On the Inductive Bias of Dropout
David P. Helmbold
UC Santa Cruz
dph@soe.ucsc.edu

Philip M. Long
Microsoft
plong@microsoft.com

arXiv:1412.4736v4 [cs.LG] 17 Feb 2015

February 18, 2015

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 the notion of when
different sources 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.

1

1

Introduction

Since its prominent role in a win of the ImageNet Large Scale Visual Recognition Challenge [Hinton, 2012,
Hinton et al., 2012], there has been intense interest in dropout (see the work by Dahl [2012], L. Deng
[2013], Dahl et al. [2013], Wan et al. [2013], Wager et al. [2013], Baldi and Sadowski [2013], Van Erven
et al. [2014]). 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
in a 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 of dropout 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 ` and dropout updates its parameter vector
w online, using stochastic gradient descent. Given an example (x, y), the dropout algorithm independently
perturbs each feature i of x: with probability 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

−xi
with probability q
νi =
(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 another and 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
def

w∗ = 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 dropout-induced distribution. (Abstracting
away sampling issues is consistent with our goal of concentrating on the inductive bias of the algorithm.
From the point of view of a bias-variance decomposition, we do not intend to focus on the large-sample-size
case, where the variance is small, but rather to focus on the contribution from the bias where P could be an
empirical sample distribution. )

2

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 is non-negative, and depends only on the marginal distribution D over the 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 in this 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 objective function 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, we
show that, despite the convexity of the dropout risk, regD,q is not convex, so that dropout provides a way to
realize the inductive bias arising from a non-convex penalty, while still enjoying the benefit of convexity in
the overall objective function (see the plots in Figures 1, 2 and 3). Figure 1 shows the even more surprising
result that the dropout regularization penalty is not even monotonic in the absolute 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 model, even if its parameter is very
large, 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; of course, the same is true for the other features. 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 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 that q, 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 accurate hypothesis for Q. This enables us to illustrate the inductive biases of the algorithms through the use of contrasting 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 another regularizer. Ensuring
that the same values of the regularization parameter are used for both P and Q controls for the amount of
3

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 a useful 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], who analyzed dropout
for random (x, y) pairs where the distribution of y given x comes from a member 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 the original loss and a term that does not depend on y, which therefore
can be viewed as a regularizer. 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 [2013] 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 by
viewing 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 of view, 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 shows that 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 unique minimizer.
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 . Section 7 provides plots demonstrating that the same distributions separated dropout from
L1 regularization. Sections 8 and 9 give separation results from L2 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. As in the introduction, if X ⊆ Rn
and P is a joint distribution over X × {−1, 1}, define
def

w∗ (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 definition
w∗ (P, q) = p argminw E(x,y)∼P,r (`(yw · (r

4

x))).

(4)

To see that they are equivalent, note that
 

r
E(`(yw · (x + ν))) = E ` yw ·

x



p

= E(`(y(w/p) · (r

x))).

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 function of w.
Similarly, we use v for the optimizer of the L2 regularized criterion:
def

v(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 , or yxi ≤ 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, and all q ∈ (0, 1),
we have that E(x,y)∼P,r (`(yw · (r x))) has a unique minimum in Rn if and only if no feature is perfect
modulo ties for P .
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 the loss 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 such that 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.

5

x = (x1 , . . . , xn )
y
w = (w1 , . . . , wn )
`(yw · x)
P, Q
D
q
p=1−q
λ
ν = (ν1 , . . . , νn )
r = (r1 , . . . , rn )
w∗ (P, q) and w∗
w~ = w∗ /p
v(P, λ) and v
regD,q (w)
J, K
g(w), g
erP (w)

feature vector in Rn
label 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.

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 ln
exp(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]
 

exp(w · (x + ν)/2) + exp(−w · (x + ν)/2)
regD,q (w) = E ln
.
exp((w · x)/2) + exp(−(w · x)/2)

6

(7)

Using a Taylor expansion, Wager et al. [2013] arrived at the following approximation:


X
x2i
q
2
.
wi Ex
w·x
2(1 − q)
(1 + exp(− w·x
2 ))(1 + exp( 2 )

(8)

i

This 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 be quite 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 regularization penalty (7) is nonnegative: for all x,

Eν


ln

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


≥ 0.

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−1

n−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)
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

Figure 1: The p = 1/2 dropout regularization for x = (1, 1) as a function of wi when the other weights are
0 together with its approximation (8) (left) and as a function of w1 for different values of the second weight
(right).
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
(10)
= (1 − p) ln(2) + p ln exp( ) + exp(
) − ln (exp(z) + exp(−z)) .
p
p
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.
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 other components are non-zero. Let w be a weight
8

vector such that for all x in the supportP
of D and dropout noise vectors ν we have |
for some bound M (this implies that | j6=i wj xj | ≤ M also). Then
!!
exp( w·(x+ν)
)+exp(− w·(x+ν)
)
2
2
regD,q (w) = Ex,ν
w·x
exp( w·x
2 )+exp(− 2 )
≤ Exi ,νi

log

≤ M +Exi ,νi

P

j6=i wj (xj + νj )|

exp( M −wi2(xi+νi ) +exp( M +wi2(xi+νi ) )

≤M

!!

i xi
i xi
exp(− M −w
+exp(− M +w
)
2
2

log

exp(− wi x2i+νi )+exp( wi (x2i+νi ) )
exp( −w2i xi )+exp( wi2xi )

!!
.

(11)

Using (11) instead of the first line in Theorem 8’s proof gives the following.
P
Proposition 10 Under the conditions of Theorem 8, if the weight vector w has the property 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).
ω

Proposition 10 shows that the regularization penalty starting from a non-zero initial weight vector 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+ν)
−w·x
Eν ln exp( 2 ) + exp(
) − ln exp( w·x
2
2 ) + 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 12 . 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 the predictions 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 proved in Appendix B.
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 .

9

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 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 ±∞.
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.
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 with bounded 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 to infinity, 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 shows that regD,q (w) does
remain bounded when multiple components of w go to infinity if the corresponding features are compatible
in the sense that the signs of wi xi are always in alignment.
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.

Discussion
The bounds in the preceding theorems and propositions suggest several properties of the dropout 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 relationship between dropout and these
algorithms, based on approximation (8). Empirical results indicate that dropout performs well in domains
like document classification where rare features can have high discriminative value [Wang and Manning,
2013]. The theorems of this section suggest that the exact dropout regularizer minimally penalizes the use
of rare 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. This intuition is reinforced by Figure 1, where the dropout penalty for
two large weights is much less then a single large weight when the features are highly correlated.
10

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, we need 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 minimizers of the dropout
and L2 -regularized criteria respectively.
∗ (P,q))
Say that sources P and Q C-separate L2 and dropout if there exist q and λ such that both ererPP(w
(v(P,λ)) >
er (v(Q,λ))

C and erQQ(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 for arbitrarily 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 follows:
x1 x2 y Pr(x, y)
10 −1 1
1/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 hypothesis, while the weight
vectors optimizing the dropout criterion make prediction errors on one-third of the distribution.
The intuition behind this behavior for the distribution described in (12) is that weight vectors 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 dropoutregularized 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.
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 defined in (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.

11

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

12

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
−1

y 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 weight on the first
feature. This means that the negative pressure on the second weight due to the (1/10, −1) data point is
much smaller (especially given its lower probability) than the positive 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 for this 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 defined in (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 18 shows 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.

7 L1 regularization
In this section, we show that the same P5 and P6 distributions that separate dropout from L2 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-opitmal
classifier on P5 , but not on P6 . Therefore the same argument shows that these distributions also strongly
separate dropout and L1 regularization.

13

Figure 3: For the source from (13) favoring the dropout, the expected loss is plotted in the upper-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) in the lower-right, all as functions of the weight vector. The Bayes-optimal
weight vectors 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 the others.)

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 is denoted with an x.

14

8

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.
Consider the source P8 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 − 1 features (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. This is 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, with its 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(P8 , λ) optimizing the L2 criterion has perfect prediction
accuracy: erP8 (v(P8 , λ)) = 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 even n > 125 then the
weight vector w∗ (P8 , q) optimizing the dropout criterion has prediction error rate erP8 (w∗ (P8 , q)) ≥ 1/10.
We conjecture that dropout fails on P8 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 the minimizer of the
dropout criteria w∗ (P8 , q) has has prediction error rate erP8 (w∗ (P8 , q)) ≥ 1/10.
Theorems 20, 21 and 22 are proved in Appendices H, I and J.

9

A high-dimensional source preferred by dropout

Define the source P9 , 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 to be 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 with probability 1/2 + β, and −y otherwise.
When η is small enough relative to β, the Bayes’ optimal prediction is to predict with the first feature.
When α is small, this requires concentrating the weight on w1 to outvote the other features. Dropout is
capable of making this one weight large while L2 regularization is not.
√
Theorem 23 If q = 1/2, n ≥ 100, α > 0, β = 1/(10 n − 1), and η ≤
η.
√
Theorem 24 If β = 1/(10 n − 1), λ =
η ∈ [0, 1], erP9 (v(P9 , λ)) ≥ 3/10.

1
30n ,

1 √
, then erP9 (w∗ (P9 , q))
2+exp(54 n)

α < βλ, and n is a large enough even number, then for any

15

=

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 9 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 shows that 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 8, 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.

10

Conclusions

We have built on the interpretation of dropout as a regularizer in Wager et al. [2013] to prove several interesting properties of the dropout regularizer. This interpretation decomposes the dropout 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 with a characterization of when the dropout criterion has a unique minimum,
and then turn to properties 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 the contribution 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 the weights 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.
In most cases the dropout regularization penalty does diverge as multiple weights go to infinity. 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 willing to 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.

16

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 the strength of regularization, a difficulty complicated
by the fact that dropout regularization is parameterized by the dropout probability q ∈ [0, 1] while L2 regularization is parameterized by λ ∈ [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 then L2 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 9 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. 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 only a single weight large. This is
consistent with the insight provided by Theorems 13 and 15.
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.

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. J. Sadowski. Understanding dropout. In Advances in Neural Information Processing Systems,
pages 2814–2822, 2013.
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. Dahl. Deep learning how i did it: Merck 1st place interview, 2012. http://blog.kaggle.com.
G. E. Dahl, T. N. Sainath, and G. E. Hinton. Improving deep neural networks for lvcsr using rectified linear
units and dropout. ICASSP, 2013.

17

A. DasGupta. Asymptotic theory of statistics and probability. Springer, 2008.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic 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. Stochastic approximation algorithms and applications. Springer, 1997.
e. a. L. Deng. Recent advances in deep learning for speech research at microsoft. ICASSP, 2013.
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.
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. I. 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. L. 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.

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 some constant 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 . Thus
regx,1/2 (w) = reg(2,2),1/2 (w1 x1 /2, w2 x2 /2).
18

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
.
(15)
2(ew2 + e−w2 )(e2w2 + e−2w2 )
The sign depends only on the numerator, which is 0 when w2 = 0. The derivative of the numerator 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 (15) is decreasing in w2 . Therefore (15) 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 whenever x 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).)

B

Proof of Theorem 13
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 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


= D(x)Eν

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|
− ln(2) +
−
.
2
2

(16)

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 (16) gives:
regD,q (ωw) > D(x) (− ln 2 + (1 − p)|ω||w2 x2 |)
which goes to infinity as ω goes to ±∞.

19

C

Proof of Theorem 15
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).

First note that If w and D are such that w · x = 0 for all x in the support of D, then regD,q (w) =
regD,q (ωw) = 0. We now analyze the general case.
regD,q (ωw) = Ex,ν
= Ex,ν

ln

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

ln

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

!!

!!


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

− (ωw · x/2) − ln (1 + exp (−ωwx)) .

(17)

Of the four terms inside the expectation in Equation (17), 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)) .
(18)
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 the contribution of these
x to the expectation in (18) 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 (18) goes to zero as
ω goes to infinity. The first term of (18) also goes to zero, unless all of the nez(w, x) components where
wi xi > 0 are dropped out. If they are all dropped out, then the first term becomes ln(2). The probability that
all nez(w, x) non-zero components are simultaneously dropped out is (1 − p)nez(w,x) . With this reasoning
we get from (18) that:
lim regD,q (ωw)

ω→∞
n
X

=



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

k=1

≤

n
X

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 19 gives a precise, but more complex expression for the limit.)

20

(19)

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 be weight vector found
by minimizing the following L2 regularized criterion J:

J(w) = 3 E(x,y)∼P (`(y(w · x))) + (λ/2)||w||2 .
(20)
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:
∂J
−10
−1.1
1
=
+
+
+ 3λw1
∂w1
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )
1
−1.1
1
∂J
+
+
+ 3λw2 .
=
∂w2
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )

(21)
(22)

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 the closed 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.
Proof: By Lemma 25, it suffices to show that there is a point (0, a2 ) where both

∂J
∂w1 (0,a2 )

< 0 and

∂J
∂w2 (0,a2 )

= 0.
From Equation (21):
∂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
∂w1 (0,a )
2

< 0 for

all a2 > −2. So, to prove the lemma, if suffices to show that there is a a2 ∈ (−2, ∞) such that the other
∂J
derivative ∂w
= 0.
2
(0,a2 )

From equation (22):
∂J
∂w2

(0,a2 )

=

2
−1.1
+
+ 3λa2
1 + exp(−a2 ) 1 + exp(1.1a2 )
∂J
∂w2 (0,a ) is
2
∂J
∂w2 (0,a2 ) = 0

and each term is continuously increasing in a2 . When a2 = −2,

negative. On the other hand,

∂J
∂w2 (0,0)

as desired.

is positive. Therefore for some a2 ∈ (−2, 0) we have

21

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

+
(a,a)

∂J(w)
∂w2

= 0.
(a,a)

Proof: Applying (21) and (22), we get
def

b=

∂J(w)
∂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 > ∞, the lemma 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 (21) and (22) at (a, a) shows that the first term of (21) is negative and the first
term of (22) is positive while the last three terms match (although 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 to show 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.
Proof: Combining

∂J
∂w1 v

3λv1 =

= 0 with (21), we get

1.1
−1
10
+
+
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
+
−
.
1 + exp(10v1 − v2 ) 1 + exp(1.1v1 − v2 ) 1 + exp(−v1 + 1.1v2 )

(23)

Assume for contraction that v1 ≥ 11v2 /10. Then 10v1 −v2 ≥ 10v2 , 1.1v1 −v2 ≥ 0.21v2 , and −v1 +1.1v2 ≤
0, so
111
22
3λ(10v1 − 11v2 ) ≤
+
− 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.
22

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 and the partial w.r.t w2
is negative.
∂J
∂w1

(x,0.6)

=

−10
−1.1
1
+
+
+ 3λx
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 > 1 such that ∂J/∂w+ (x,1) = 0.
∂J
∂w2

(x,0.6)

=

1
1
−1.1
+
+
+ 1.8λ
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 = 1 and λ = 1/50, so it will remain
negative for all x > 1 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.

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))))

(24)

where the components of r are independent samples from a Bernoulli distribution with parameter p =
1 − q > 0. Again, the factor of 3 is to simplify the expectation and doesn’t change 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 an example 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 we are 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 value of wi does not
matter.)


∂J
−10
−1.1
1
2
= (1 − q)
+
+
(25)
∂w1
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )


−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)
+
+
(26)
∂w2
1 + exp(10w1 − w2 ) 1 + exp(1.1w1 − w2 ) 1 + exp(−w1 + 1.1w2 )


1
1
−1.1
+ q(1 − q)
+
+
.
1 + exp(−w2 ) 1 + exp(−w2 ) 1 + exp(1.1w2 )
23

The following is the key lemma. As before, it is useful since, for any w, if g(w) is nonzero, 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.

(27)

(a,10a/11)

Proof: We have
∂J
∂w2

(a,10a/11)



1
1
−1.1
=(1 − q)
+
+
1 + exp(100a/11) 1 + exp(21a/110)
2


2
−1.1
+ q(1 − q)
.
+
1 + exp(−10a/11) 1 + exp(a)
2



Note that this derivative is positive if and only if


∂J
1
f (q, a) =
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
−11
1
+
+
+
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 to 0 when a = 0. On
the other hand, the terms not multiplied by q are decreasing in a and turn negative when a is just over 1/4.
Thus both parts are positive when a ≤ 1/4. Note that 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,


11
2
−1
−1
−11/10
f (q, a) ≥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,


11
2
−1
−1
−11/10
−11
f (q, a) ≥ 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
24

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 the proof.

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 correctly classify
(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 .

(28)

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 )
∂J
−3
1
=
+
+ 7λw2 .
∂w2
1 + exp(−w1 + w2 ) 1 + exp(w1 /10 − w2 )

(29)
(30)

Lemma 32 If either: λ ≥ 1/100 and a ≥ 1/3, or λ ≥ 1/4 and a ≥ 1/15 then
∂J(w)
∂w1

(10a,a)

> 0.

Proof: We have
∂J(w)
∂w1

=
(10a,a)

−3
3
−1
−3
−1
+
+
+ 70λa >
+
+ 70λa.
(1 + exp(10a)) 1 + exp((1 − 10)a) 20
(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.

25

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/1000
0
−1/1000
1
0
−1
1/10
0
1/10
−1

y
seven times probability
w~ · (r
1
3q
+3q 2
+q 2
1 3(1 − q)
1
3q(1 − q)
1
3q(1 − q)
1
3(1 − q)2
1
q(1 − q)
1
q(1 − q)
1
(1 − q)2

x) over-estimate
0
∞
w2
0
w2
∞
∞
∞

Proof: Assume to the contrary that λ ≤ 1/4 but v2 < 1/3. From (30), and using that v1 > 0, we have
∂J
∂w2

<
v

1
−3
+
+ 7λv2 ,
1 + exp(v2 ) 1 + exp(−v2 )

a bound that is increasing in v2 and λ. Since

∂J
∂w2 v

(31)

= 0, the bound must be positive. However, when

v2 ≤ 1/3 and λ ≤ 1/4, it is negative, giving the desired contradiction.
Since the bound (31) 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 minimizing v (when
λ ≥ 1/100), so by convexity,

J(10v2 , v1 ) + (v1 , v2 ) − (10v2 , v2 ) · ∇J(10v2 , v2 ) < J(v1 , v2 )
(32)
(v1 − 10v2 )

∂J
∂w2

< 0.

(33)

(10v2 ,v2 )

If 1/100 ≤ λ ≤ 1/4 then Lemma 33 shows that v2 ≥ 1/3 and if 1/4 ≤ λ ≤ 1 then it shows that
∂J
v2 ≥ 1/15. In either case, Lemma 32 shows that that ∂w
> 0. Therefore,
2
(10v2 ,v2 )

v1 < 10v2
and (0.1, −1) is misclassified by v, completing the proof.

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 · (r
26

x)))),

(34)

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 function by 7 does not change
the minimizer of J.) See Table 2 for a tabular representation of the distribution after dropout. Let w~ be the
minimizer of J, so that w∗ = pw~ (see Equation (4)).
First, let us evaluate some partial derivatives (note that 1 − q = (1 − q)2 + q(1 − q)).


∂J
−3
3
−0.1
2
= (1 − q)
(35)
+
+
∂w1
1 + exp(w1 ) 1 + exp(−w1 + w2 ) 1 + exp(0.1w1 − w2 )


3
−0.1
−3
+
+
+ (1 − q)q
1 + exp(w1 ) 1 + exp(−w1 ) 1 + exp(0.1w1 )


∂J
−3
1
2
= (1 − q)
+
(36)
∂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
∂J
< 0 and ∂w
Proof: As before, it suffices to show that there is a point (0, a2 ) where both ∂w
1 (0,a2 )
2
0.
From Equation (35):


∂J
3
−0.1
(1 − q)q
2 −3
= (1 − q)
+
+
+
(−3.1 + 3)
∂w1 (0,a2 )
2
1 + exp(a2 ) 1 + exp(−a2 )
2

which is decreasing in a2 , and negative even as a2 approaches −∞ (recalling  = 1/1000), so

(0,a2 )

∂J
∂w1 (0,a )
2

=

is

always negative.
Equation (36) implies




−3
1
−3
1
∂J
2
= (1 − q)
+
+ q(1 − q)
+
.
∂w2 (0,a2 )
1 + exp(a2 ) 1 + exp(−a2 )
1 + exp(a2 ) 1 + exp(−a2 )
This is negative when a2 = 0, approaches 1 − q as a2 goes to infinity, and is continuous, so there is a a2
∂J
∂J
such that ∂w
= 0. Since ∂w
< 0, this proves the lemma.
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 (35), we have
∂J
∂w1

(a/,a)


−3
3
−0.1
+
+
1 + exp(a/) 1 + exp(0) 1 + exp(0.1(a/) − a)


−3
3
−0.1
+ q(1 − q)
+
+
1 + exp(a/) 1 + exp(−a) 1 + exp(a/10)

=(1 − q)2



which is positive if a > 1/10 as the positive terms (even with the  factors) dominate the negative ones.
27

Lemma 36
w2~ > 1/4.
Proof: Assuming w1 ≥ 0, the estimates in Table 2 along with the facts that `(z) is positive and decreasing
show :
J(w) ≥ 3(1 − q) ln(1 + exp(−w2 )) + 6q ln(2) + q 2 ln(2)
(37)
which is decreasing in w2 . If w2~ ≤ 1/4, then bound (37) 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 and 36, g 6= (0, 0), so
w~ · g < (w2~ /, w2~ ) · g.
This implies
w1~

∂J
∂w1

(w2~ /,w2~ )

<

w2~ ∂J
 ∂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
∂w1

(10a,a)

< 0.

Proof: Choose a ∈ R. From (35), we have


−3
∂J
3
−1
= q(1 − q)
+
+
∂w1 (10a,a)
1 + exp(10a) 1 + exp(−10a) 10(1 + exp(a))


−3
3
−1
2
+ (1 − q)
+
+
1 + exp(10a) 1 + exp(a − 10a)
20


−1
≤ (1 − q)2 6 +
<0
20
using q ≤ 1/2 and  = 1/1000.
Lemma 39 w1~ > 10w2~ .

28

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

u

∂J
∂w1

u

< 10w2~

∂J
∂w1

u

.

< 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~ , and therefore by
= pw~ . Lemma 37 implies that (−, 1) is classified correctly. Lemma 39 implies that (1/10, −1) is
classified correctly, completing the proof.
w∗

H

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

In this proof, let us abbreviate P8 as just P .
By symmetry and convexity, the optimizing v is of the form (v1 , v2 , v2 , . . . , v2 ) with the last 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 .
10
10
2

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:
∂K
−9
1
=
+
+ λ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 ))

(38)
(39)

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 .
To prove v1 < v2 we show the existence of a point (a, a) such that
∂K
∂w1

=−
(a,a)

∂K
∂w2

29

> 0,
(a,a)

(40)

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

∂K
∂w1

(a,a)

=

−9
1
+
+ λa
10(1 + exp(2a)) 20

which is increasing in a, negative when a = 0 and goes to infinity with a. It turns positive at 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
of ∂K/∂w1

(a,a)

(a,a)

crosses zero until ∂K/∂w2

is increasing, starting at 0, and the magnitude of ∂K/∂w2

(a,a)

(a,a)

(a,a)

does, the magnitude

is decreasing until it reaches

0. When they meet, Equation (40) holds, completing the proof.

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∗ (P8 , q) optimizing the dropout criterion has prediction error rate
erP8 (w∗ (P8 , q)) ≥ 1/10.

In this proof, we again abbreviate, using P for P8 .
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 is fruitless, and a key step is to apply
Jensen’s inequality on just half the distribution resulting from dropout.
Similarly to before, let
J(w) = E(x,y)∼P,r (`(y(w · (r x)))),
(41)
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 (41) is positive.

30

gr be the marginal distribution of the last n − 1 components after dropout and x̃ denote these
Proof: Let P,
last n − 1 components of the dropped-out feature vector. Then, recalling y is always 1 in our distribution
(and p is the probability that the first feature is not dropped out),


9p
∂J(w)
p
0
0
= E(r2 ,...,rn )
E f (` (w · (1, x̃))) − Ex̃∼P,r
f (` (w · (−1, x̃)))
∂w1
10 x̃∼P,r
10
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 to a 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, since w2~ ≤ 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.51
2
20
20

contradicting 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 negative ones (as in P ), but x1 is
always one. Since 0 < w1~ ≤ w2~ and the label y = 1 under P and P1 ,
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). Therefore
E(x,y)∼P1 ,r (w2~ (x · r)) = Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1)))
giving the desired bound.
31


Lemma 43 For even n ≥ 6, Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) ≥ 31 ` w2~ −
Pn/2−1

√ 
w2~ 2n
.
4

n
i

, so α is slightly less than 2n−1 .
 
1 X n
~
`(w2~ (k + 1 − (n/2)))
Ek∼B(n,1/2) (`(w2 (k − (n/2) + 1))) = n
k
2

Proof: Let α =

i=0



k

n/2−1

 
α X 1 n
`(w2~ (1 + k − (n/2)))
> n
2
α 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,


~ n/2−1
X n
α
w
Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) > n ` w2~ + 2
(k − (n/2)) .
2
α
k
k=0

Equation (5.18) of Concrete Mathematics Graham et al. [1989] and the bound

n
n/2



≥

n
√2
2n

give

√



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

n/2−1 

X
k=0

Therefore, recalling that α < 2n−1 and noting α/2n > 1/3 when n ≥ 6,
√ !
~ n−1
2n
2
α
w
Ek∼B(n,1/2) (`(w2~ (k − (n/2) + 1))) > n ` w2~ − 2
2
α
4
!
√
w~ 2n
1
.
> ` w2~ − 2
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.31
4
√
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) < 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 and q = 1/2 we conjecture that
optimizing the dropout criterion fails to produce the Bayes optimal hypothesis for every even n ≥ 4.
32

Table 3: Probabilities of x1 r1 and
x1 r1
1
0
-1

J

P4

i=2 xi ri

probability
9/20
1/2
1/20

values assuming dropout probability q = 1/2.
P4
probability
i=2 xi ri
2
1/8
1
3/8
0
3/8
-1
1/8

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∗ (P8 , q) has has prediction error rate erP8 (w∗ (P8 , q)) ≥
1/10.

In this proof, let us also refer to P8 as just P and let w~ be the minimizer of (41).
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 P
can be written with 12 terms, one for each pairing of the three possible x1 r1 values with
the four possible 4i=2 xi ri ∈ {−1, 0, 1, 2} values (see Table 3).
Taking them in order, we have
K(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

So, when p = q = 1/2, the derivatives are:
−9
−27
−27
−9
∂K
=
+
+
+
∂w1
1 + exp(w1 + 2w2 ) 1 + exp(w1 + w2 ) 1 + exp(w1 ) 1 + exp(w1 − w2 )
!
.
1
3
3
1
+
+
+
+
160,
1 + exp(−w1 + 2w2 ) 1 + exp(−w1 + w2 ) 1 + exp(−w1 ) 1 + exp(−w1 − w2 )
∂K
−18
−27
9
=
+
+
∂w2
1 + exp(w1 + 2w2 ) 1 + exp(w1 + w2 ) 1 + exp(w1 − w2 )
+

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

!
.
−2
−3
1
+
+
+
160.
1 + exp(−w1 + 2w2 ) 1 + exp(−w1 + w2 ) 1 + exp(−w1 − w2 )
33

∇K = (−c, c)

w2
(a, a)
−∇K = (c, −c)

w1
Figure 5: If ∇K at some (a, a) is (−c, c) for some c > 0 then w1~ > w2~ .
If w1~ > w2~ , then dropout will have prediction error rate 1/10 as w1~ will dominate the vote of the other
three components. We show that w1~ > w2~ by proving that there is a point (a, a) in weight space such that
the gradient at (a, a) is of the form (−c, c) for some c > 0 (see Figure 5).
The derivatives when evaluated at (a, a) are:
!
.
∂K
−9
−27
−26
3
1
+
+
−3+
+
160
=
∂w1
1 + exp(3a) 1 + exp(2a) 1 + exp(a)
1 + exp(−a) 1 + exp(−2a)
(a,a)
!
.
∂K
−18
−47
−32
10
1
=
+
+
+3+
+
160.
∂w2
1 + exp(3a) 1 + exp(2a) 1 + exp(a)
1 + exp(−a) 1 + exp(−2a)
(a,a)

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.

K

Proof of Theorem 23
√
Theorem 23. If q = 1/2, n ≥ 100, α > 0, β = 1/(10 n − 1), and η ≤
erP9 (w∗ (P9 , q)) = η.

1 √
,
2+exp(54 n)

then

For this subsection, let P = P9 and define the scaled dropout criterion
J(w) = E(x,y)∼P,r (`(yw · (r

x))),

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 conditioned on the label y = 1.
Let B = {2, ..., n}. By symmetry, wi~ is identical for all i ∈ B so w~ is the minimum of J over
weight vectors satisfying this constraint. Let K(w1 , w2 ) = J(w1 , w2 , ..., w2 ); note that w1~ , w2~ minimizes
K defined by
X
K(w1 , w2 ) = Ex∼D,r (`(w1 r1 x1 + w2
ri xi )).
i∈B

34

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

(42)

since when (42) holds, w~ always outputs x1 .
We have


1
−x1
∂K
P
= Ex∼D,r
∂w1
2
1 + exp(w1 x1 + w2 i∈B ri xi )
P


− i∈B ri xi
∂K
P
= Ex∼D,r
.
∂w2
1 + exp(w1 r1 x1 + w2 i∈B ri xi )

(43)
(44)

(Note that, in (43), 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)
From equation (44),
P


− i∈B ri xi
∂K
<0
= Ex∼D,r
∂w2 (a1 ,0)
1 + exp(a1 r1 x1 )

∂K
∂w1 (a1 ,0)

= 0.

for all real a1 .
Now, evaluating (43), dividing into cases based on x1 , we get




∂K
−α
α
+ ((1 − η)/2)
.
= (η/2)
∂w1 (a1 ,0)
1 + exp(−αa1 )
1 + exp(αa1 )
This approaches −α((1 − η)/2) as a1 approaches −∞, and it approaches αη/2 as a1 approaches ∞. Since
∂K
it is a continuous function of a1 , there must be a value of a1 such that ∂w
= 0. Putting this together
1 (a1 ,0)
with

∂K
∂w2 (a1 ,0)

< 0 completes the proof.

To show the sufficient inequalities (42), 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, we want 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 of an error from Helmbold and Long [2012].
To simplify the proof, we will first provide a lower bound on the dropout risk in terms of the risk without
dropout. We will actually prove something somewhat more general, for possible future reference.
Lemma 45 Let r and x be independent, RN -valued random variables; let φ be convex function of a scalar
real variable. Then
!!
!!
X
X
Er,x φ
xi ri
≥ Ex φ
xi Er (ri )
.
i

i

35

Proof: Since x and r are independent,
X
Er,x (φ(
xi ri ))
i

X
= Ex (Er (φ(
xi ri )))
i

X
≥ Ex (φ(Er (
xi ri ))) (by Jensen’s Inequality)
i

X
= Ex (φ(
xi Er (ri ))),
i

completing 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}.
!
1 X
3
Lemma 46 Pr
xi < −2β ≥ .
n−1
10
i∈B

Proof: If Z is a standard normal random variable and R is a binomial (`, p) random variable with p ≤ 1/2,
then for `(1 − p) ≤ j ≤ `p, Slud’s inequality Slud [1977] (see also Lemma 23 of Helmbold and Long
[2012]) gives
!
j − `p
Pr(R ≥ j) ≥ Pr Z ≥ p
.
(45)
`p(1 − p)
Now, we have
Pr

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∈B

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

i∈B

!
= Pr

X
i∈B

36

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

Using (45) with j = (n − 1)(1/2 + β), ` = (n − 1), and p = 1/2 − β gives:
!
!
X
(n − 1)(1/2 + β) − (n − 1)(1/2 − β)
p
Pr
z̄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
Pr
xi < −2β ≥ Pr(Z ≥ 0) − Pr(Z ∈ (0, 1/2)) > − √ > 3/10,
n−1
2 2 2π
i∈B
completing 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 − 1
K(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
X
1
xi
K(w1 , w2 ) ≥ E ` (w2 /2)
2

!!
.

i∈B

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

1 X
xi < −2β
n−1
i∈B

and applying Lemma 46 gives
K(w1 , w2 ) ≥

3`(−w2 β(n − 1))
.
20

Since `(z) > −z, we have
K(w1 , w2 ) ≥
and, using β =

√1
,
10 n−1

we get

3w2 β(n − 1)
20

√
3w2 n − 1
K(w1 , w2 ) ≥
,
200

completing the proof.
37

!
,

Lemma 48 w2~ <

√27 .
n−1

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

(46)

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

√
w2 n − 1
>
.
67

Solving for w2~ completes the proof.
Lemma 49 For all 0 < u <

√27 ,
n−1

we have
∂K
∂w1

((n−1)u/α,u)

< 0.

Proof: From (43), we have
2

∂K
∂w1

(nu/α,u)


−x1
P
= Ex∼D,r
1 + exp((n − 1)ux1 /α + u i∈B ri xi )




α
−α
P
P
= ηEx∼D,r
+ (1 − η)Ex∼D,r
1 + exp(−(n − 1)u + u i∈B ri xi )
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.


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 · g
which, since u2 = w2~ , implies

w1~ g1 < (n − 1)w2~ g1 /α.
38

Since, by Lemmas 48 and 49, g1 < 0,
w1~ > (n − 1)w2~ /α
completing the proof.

L

Proof of Theorem 24
√
1
Theorem 24. If β = 1/(10 n − 1), λ = 30n
, α < βλ, and n is a large enough even number,
then for any η ∈ [0, 1], erP9 (v(P9 , λ)) ≥ 3/10.

In this proof, let us also abbreviate P9 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 the more 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 of x under P conditioned on y = 1.
!!
X
λ
xi
+ (w12 + (n − 1)w22 ).
K(w1 , w2 ) = Ex∼D ` w1 x1 + w2
2
i∈B

Lemma 46, together with the fact that |x1 | = α, implies that,
αv1 < 2β(n − 1)v2

(47)

suffices to prove Theorem 24, so we set this as our subtask.
We have


∂K
−x1
P
+ λw1
= Ex∼D
∂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 .
Lemma 51 |v1 | ≤

α
λ

< β.

Proof: The second inequality follows from the constraint on α. From (48), we get


x1
1
P
|v1 | ≤ Ex∼D
λ
1 + exp(v1 x1 + v2 i∈B xi )
and the facts |x1 | ≤ α and 0 <

1 P
1+exp(v1 x1 +v2 i∈B xi )

≤ 1 then imply |v1 | ≤ α/λ.

Lemma 52 For large enough n,
!
Pr

X

xi ∈ [β(n − 1), 3β(n − 1)]

i∈B

39

≥

1
.
13

(48)
(49)

P
Proof: Let Φ(z) = Pr(Z ≤ z) for a standard normal random variable Z and let S = i∈B xi . Note that
E(xi ) = 2β, var(xi ) = 1 − 4β 2 , and the third moment E(|xi − E(xi )|3 ) = 1 − 16β 4 . 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
S
C(1 − 16β 4 )
1 − 4β 2
1
√
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:
!
1
s − 2β(n − 1)
sup Pr (S ≤ s) − Φ p
≤√
,
n−1
s
(1 − 4β 2 )(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



2
−1 1
,
−√
≥ Prz∈N (0,1) z ∈
10 10
n−1
1
≥ ,
13
for large enough n.
shows that the Berry-Esseen constant C is less then 1/2, this allows us to replace the
√ Recent work √
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 .
Lemma 53 v2 ≥

1
n−1 .

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

P

i∈B



P

xi
P
1 + exp(v1 x1 + v2 i∈B xi )
i∈B

xi by S, then
v2 =

1
Ex∼D
λ(n − 1)



S
1 + exp(v1 x1 + v2 S)

Since, for all odd3 s > 0
Pr(S = s)
=
Pr(S = −s)
3



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

40

1 + 2β
1 − 2β

s


.


.

so Pr(S = −s) = Pr(S = s)

v2 λ(n − 1) =

n−1
X



1−2β
1+2β

s


Pr(S = s) (1 − η)

s=1

. Analyzing the contributions of s and −s together we have

s
s
+η
1 + exp(v1 α + v2 s)
1 + exp(−v1 α + v2 s)


+ (1 − η)

−s
−s
+η
1 + exp(v1 α − v2 s)
1 + exp(−v1 α − v2 s)



1 − 2β
1 + 2β

s 

Recalling that |v1 | ≤ α/λ (Lemma 51), and using the minimizing value in this range for each term gives
n−1
X



 
s
−s
1 − 2β s
v2 λ(n − 1) ≥
Pr(S = s)
+
1 + exp(α2 /λ + v2 s)
1 + exp(−α2 /λ − v2 s)
1 + 2β
s=1
s 


1−2β
n−1
1 − exp(α2 /λ + v2 s) 1+2β
X


=
Pr(S = s)s
1 + exp(α2 /λ + v2 s)


s=1

≥

n−1
X


Pr(S = s)s

s=1

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


.

Assume for contradiction that v2 < 1/(n − 1). Then,
n−1
X


1 − exp(α2 /λ + s/(n − 1) − 4βs)
v2 λ(n − 1) ≥
Pr(S = s)s
1 + exp(α2 /λ + s/(n − 1))
s=1


n−1
X
1 − exp(s/(n − 1) − 3βs)
(since α ≤ βλ)
≥
Pr(S = s)s
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


1
1 − exp(−2β 2 (n − 1))
1
v2 ≥
×
× β(n − 1)
λ(n − 1) 13
1 + exp(β 2 λ + 3β)
√


30 n − 1
1 − exp(−1/50)
√
=
.
(50)
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 (50) 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.
41

.

Now we’re ready to put everything together.
Proof (of Theorem 24): Recall that, by Lemma 46, if v1 < 2β(n − 1)v2 , then erP (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.

42

