Journal of Machine Learning Research v (2012) pp

Submitted sub; Published pub

On the Necessity of Irrelevant Variables
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@sv.nec-labs.com

NEC Labs America
10080 N. Wolfe Rd, SW3-350
Cupertino, CA 95014, USA

Editor: Gábor Lugosi

Abstract
This work explores the effects of relevant and irrelevant boolean variables on the accuracy of classifiers. The analysis uses the assumption that the variables are conditionallyindependent given the class, and focuses on a natural family of learning algorithms forsuch sources when the relevant variables have a small advantage over random guessing.
The main result is that algorithms relying predominately on irrelevant variables have error probabilities that quickly go to 0 in situations where algorithms that limit the useof irrelevant variables have errors bounded below by a positive constant. We also showthat accurate learning is possible even when there are so few examples that one cannot
determine with high confidence whether or not any individual variable is relevant.
Keywords: Feature Selection, Generalization, Learning Theory

1. Introduction
When creating a classifier, a natural inclination is to only use variables that are obviously
relevant since irrelevant variables typically decrease the accuracy of a classifier. On theother hand, this paper shows that the harm from irrelevant variables can be much lessthan the benefit from relevant variables and therefore it is possible to learn very accurateclassifiers even when almost all of the variables are irrelevant. It can be advantageous tocontinue adding variables, even as their prospects for being relevant fade away. We show
this with theoretical analysis and experiments using artificially generated data.
We provide an illustrative analysis that isolates the effects of relevant and irrelevant
variables on a classifier’s accuracy. We analyze the case in which variables complement one
another, which we formalize using the common assumption of conditional independence
given the class label. We focus on the situation where relatively few of the many variables
are relevant, and the relevant variables are only weakly predictive.1 Under these conditions,algorithms that cast a wide net can succeed while more selective algorithms fail.
1. Note that in many natural settings the individual variables are only weakly associated with the classlabel. This can happen when a lot of measurement error is present, as is seen in microarray data.
c 2012 David P. Helmbold and Philip M. Long.

Helmbold and Long

We prove upper bounds on the error rate of a very simple learning algorithm that
may include many irrelevant variables in its hypothesis. We also prove a contrasting lower
bound on the error of every learning algorithm that uses mostly relevant variables. The
combination of these results show that the simple algorithm’s error rate approaches zero insituations where every algorithm that predicts with mostly relevant variables has an error
rate greater than a positive constant.
Over the past decade or so, a number of empirical and theoretical findings have challenged the traditional rule of thumb described by Bishop (2006) as follows.
One rough heuristic that is sometimes advocated is that the number of data
points should be no less than some multiple (say 5 or 10) of the number ofadaptive parameters in the model.
The Support Vector Machine literature (see Vapnik, 1998) views algorithms that computeapparently complicated functions of a given set of variables as linear classifiers applied toan expanded, even infinite, set of features. These empirically perform well on test data,
and theoretical accounts have been given for this. Boosting and Bagging algorithms also
generalize well, despite combining large numbers of simple classifiers – even if the number ofsuch “base classifiers” is much more than the number of training examples (Quinlan, 1996;
Breiman, 1998; Schapire et al., 1998). This is despite the fact that Friedman et al. (2000)
showed the behavior of such classifiers is closely related to performing logistic regression ona potentially vast set of features (one for each possible decision tree, for example).
Similar effects are sometimes found even when the features added are restricted to theoriginal “raw” variables. Figure 1, which is reproduced from (Tibshirani et al., 2002), is
one example. The curve labelled “te” is the test-set error, and this error is plotted as afunction of the number of features selected by the Shrunken Centroids algorithm. The best
accuracy is obtained using a classifier that depends on the expression level of well over 1000
genes, despite the fact that there are only a few dozen training examples.
It is impossible to tell if most of the variables used by the most accurate classifier inFigure 1 are irrelevant. However, we do know which variables are relevant and irrelevant
in synthetic data (and can generate as many test examples as desired). Consider for the
moment a simple algorithm applied to a simple source. Each of two classes is equally
likely, and there are 1000 relevant boolean variables, 500 of which agree with the class labelwith probability 1/2 + 1/10, and 500 which disagree with the class label with probability
1/2 + 1/10. Another 99000 boolean variables are irrelevant. The algorithm is equallysimple: it has a parameter β, and outputs the majority vote over those features (variablesor their negations) that agree with the class label on a 1/2 + β fraction of the training
examples. Figure 2 plots three runs of this algorithm with 100 training examples, and 1000
test examples. Both the accuracy of the classifier and the fraction of relevant variables
are plotted against the number of variables used in the model, for various values of β.2
Each time, the best accuracy is achieved when an overwhelming majority of the variables
used in the model are irrelevant, and those models with few (< 25%) irrelevant variables
perform far worse. Furthermore, the best accuracy is obtained with a model that uses many
2. In the first graph, only the results in which fewer than 1000 features were chosen are shown, sinceincluding larger feature sets obscures the shape of the graph in the most interesting region, whererelatively few features are chosen.

2Necessity of Irrelevant Variables

Figure 1: This graph is reproduced from (Tibshirani et al., 2002). For a microarray dataset,the training error, test error, and cross-validation error are plotted as a function
both of the number of features (along the top) included in a linear model and a
regularization parameter ∆ (along the bottom).

3Helmbold and Long

Figure 2: Left: Test error (blue) and fraction of irrelevant variables (black) as a function of
the number of features. Right: Scatter plot of test error rates (vertical) against
fraction of irrelevant variables (horizontal).

more variables than there are training examples. Also, accuracy over 90% is achieved eventhough there are few training examples and the correlation of the individual variables withthe class label is weak. In fact, the number of examples is so small and the correlations are
so weak that, for any individual feature, it is impossible to confidently tell whether or not
the feature is relevant.
Assume classifier f consists of a vote over n variables that are conditionally independent
given the class label. Let k of the variables agree with the class label with probability
1/2 + γ, and the remaining n − k variables agree with the label with probability 1/2. Thenthe probability that f is incorrect is at most
−2γ 2 k 2
exp
(1)n
(as shown in Section 3). The error bound decreases exponentially in the square of thenumber of relevant variables. The competing factor increases only linearly with the numberof irrelevant variables. Thus, a very accurate classifier can be obtained with a feature set
consisting predominantly of irrelevant variables.
In Section 4 we consider learning from training data where the variables are conditionallyindependent given the class label. Whereas Equation (1) bounded the error as a functionof the number of variables n and relevant variables k in the model, we now use capital
N and capital K for the total number of variables and number of relevant variables inthe data. The N − K irrelevant variables are independent of the label, agreeing with itwith probability 1/2. The K relevant variables either agree with the label with probability
1/2 + γ or with probability 1/2 − γ. We analyze an algorithm that chooses a value β ≥ 0
and outputs a majority vote over all features that agree with the class label on at least
1/2 + β of the training examples (as before, each feature is either a variable or its negation).
Our Theorem 3 shows that if β ≤ γ and the algorithm is given m training examples, thenthe probability that it makes an incorrect prediction on an independent test example is at
4

Necessity of Irrelevant Variables

most

2

(1 + o(1)) exp −2γ 2 K[1 − 8e−2(γ−β) m − γ)]2+
1 + 8(N/K)e−2β 2 m + γ

!!
,

(2)

def

where [z]+ = max{z, 0}. (Throughout the paper, the “big Oh” and other asymptotic
notation will be for the case where γ is small, Kγ is large, and N/K is large. Thus the edgeof the relevant features and the fraction of features that are relevant both approach zero
while the total number of relevant features increases. If K is not large relative to 1/γ 2 , even
the Bayes optimal classifier is not accurate. No other assumptions about the relationshipbetween the parameters are needed.)
When β ≤ γ/2 and the number m of training examples satisfies m ≥ c/γ 2 for an absolute
constant c, we also show in Theorem 8 that the error probability is at most
(1 + o(1)) exp −γ 2 K 2 /N .
(3)
If N = o(γ 2 K 2 ), this error probability goes to zero. With only Θ(1/γ 2 ) examples, analgorithm cannot even tell with high confidence whether a relevant variable is positively
or negatively associated with the class label, much less solve the more difficult problem ofdetermining whether or not a variable is relevant. Indeed, this error bound is also achieved
using β = 0, when, for each variable Xi , the algorithm includes either Xi or its negation in
the vote.3 Because bound (3) holds even when β = 0, it can be achieved by an algorithm
that does not use knowledge of γ or K.
Our upper bounds illustrate the potential rewards for algorithms that are “inclusive”,
using many of the available variables in their classifiers – even when this means that mostvariables in the model are irrelevant. We also prove a complementary lower bound that
illustrates the potential cost when algorithms are “exclusive”. We say that an algorithmis λ-exclusive if the expectation of the fraction of the variables used in its model that are
relevant is at least λ. We show that any λ-exclusive policy has an error probability bounded
below by λ/4 as K and N/K go to infinity and γ goes to 0 in such a way that the error rate
obtained by the more “inclusive” setting β = γ/2 goes to 0. In particular, no λ-exclusive
algorithm (where λ is a positive constant) can achieve a bound like (3).
Relationship to Previous Work Donoho and Jin (see Donoho and Jin, 2008; Jin,
2009) and Fan and Fan (2008), building on a line of research on joint testing of multiple
hypotheses (see Abramovich et al., 2006; Addario-Berry et al., 2010; Donoho and Jin, 2004,
2006; Meinshausen and Rice, 2006), performed analyses and simulations using sources withelements in common with the model studied here, including conditionally independent variables and a weak association between the variables and the class labels. Donoho and Jin also
pointed out that their algorithm can produce accurate hypotheses while using many more
irrelevant features than relevant ones. The main theoretical results proved in their papers
describe conditions that imply that, if the relevant variables are too small a fraction of all
the variables, and the number of examples is too small, then learning is impossible. The
3. To be precise, the algorithm includes each variable or its negation when β = 0 and m is odd, and includes
both the variable and its negation when m is even and the variable agrees with the class label exactly
half the time. But, any time both a variable and its negation are included, their votes cancel. We will
always use the smaller equivalent model obtained by removing such canceling votes.

5Helmbold and Longemphasis of our theoretical analysis is the opposite: algorithms can tolerate a large numberof irrelevant variables, while using a small number of examples, and algorithms that avoid
irrelevant variables, even to a limited extent, cannot learn as effectively as algorithms thatcast a wider net. In particular, ours is the first analysis that we are aware of to have a result
qualitatively like Theorem 13, which demonstrates the limitations of exclusive algorithms.
For the sources studied in this paper, there is a linear classifier that classifies mostrandom examples correctly with a large margin, i.e. most examples are not close to thedecision boundary. The main motivation for our analysis was to understand the effects
of relevant and irrelevant variables on generalization, but it is interesting to note that we
get meaningful bounds in the extreme case that m = Θ(1/γ 2 ), whereas the margin-based
bounds that we are aware of (such as Schapire et al. (1998); Koltchinskii and Panchenko(2002); Dasgupta and Long (2003); Wang et al. (2008)) are vacuous in this case. (Since theseother bounds hold more generally, their overall strength is incomparable to our results.) Ng
and Jordan (2001) showed that the Naive Bayes algorithm (which ignores class-conditional
dependencies) converges relatively quickly, justifying its use when there are few examples.
But their bound for Naive Bayes is also vacuous when m = Θ(1/γ 2 ). Bickel and Levina(2004) studied the case in which the class conditional distributions are Gaussians, andshowed how an algorithm which does not model class conditional dependencies can performnearly optimally in this case, especially when the number of variables is large. Bühlmann
and Yu (2002) analyzed the variance-reduction benefits of Bagging with primary focus on
the benefits of the smoother classifier that is obtained when ragged classifiers are averaged.
As such it takes a different form than our analysis.
Our analysis demonstrates that certain effects are possible, but how important this isdepends on how closely natural learning settings resemble our theoretical setting and theextent to which our analysis can be generalized. The conditional independence assumption
is one way to express the intuitive notion that variables are not too redundant. A limiton the redundancy is needed for results like ours since, for example, a collection of Θ(k)perfectly correlated irrelevant variables would swamp the votes of the k relevant variables.
On the other hand, many boosting algorithms minimize the potential for this kind of effectby choosing features in later iterations that make errors on different examples then thepreviously chosen features. One relaxation of the conditional independence assumption is
to allow each variable to conditionally depend on a limited number r of other variables, as
is done in the formulation of the Lovasz Local Lemma (see Alon et al., 1992). As partial
illustration of the robustness of the effects analyzed here, we generalizeupper bound(1) to−2γ 2 k2
this case in Section 6.1. There we prove an error bound of c(r + 1) exp n(r+1) when eachvariable depends on most r others. There are a number of ways that one could imagine
relaxing the conditional independence assumption while still proving theorems of a similar
flavor. Another obvious direction for generalization is to relax the strict categorization ofvariables into irrelevant and (1/2 + γ)-relevant classes. We believe that many extensions of
this work with different coverage and interpretability tradeoffs are possible. For example,
our proof techniques easily give similar theorems when each relevant variable has a probability between 1/2 + γ/2 and 1/2 + 2γ of agreeing with the class label (as discussed in
Section 6.2). Most of this paper uses the cleanest and simplest setting in order to focus
attention on the main ideas.
6

Necessity of Irrelevant Variables

We state some useful tail bounds in the next section, and Section 3 analyzes the error of
simple voting classifiers. Section 4 gives bounds on the expected error of hypotheses learned
from training data while Section 5 shows that, in certain situations, any exclusive algorithm
must have high error while the error of some inclusive algorithms goes to 0. In Section 6.1
we bound the accuracy of voting classifiers under a weakened independence assumption andin Section 6.2 we consider relaxation of the assumption that all relevant variables have thesame edge.

2. Tail bounds
This section gathers together the several tail bounds that will be used in various places in
the analysis. These boundsP
all assume that U1 , U2 , . . . , U` are ` independent {0, 1}-valued
random variables and U = `i=1 Ui . We start with some upper bounds.
• The Hoeffding bound, (see Pollard, 1984):




1
1
2
P U −EU ≥ η ≤ e−2η ` .
`
`

(4)

• The Chernoff bound, (Angluin and Valiant, 1979; Motwani and Raghavan, 1995, see)and Appendix A.1. For any η > 0:



1+η
P[U > (1 + η)E(U )] < exp −(1 + η)E(U ) ln.
(5)e
• For any 0 ≤ η ≤ 4 (see Appendix A.1):

P[U > (1 + η)E(U )] < exp −η 2 E(U )/4 .

(6)• For any 0 < δ ≤ 1 (see Appendix A.2):
P[U > 4E(U ) + 3 ln(1/δ)] < δ.

(7)

We also use the following lower bounds on the tails of distributions.
• If P[Ui = 1] = 1/2 for all i, η > 0, and ` ≥ 1/η 2 then (see Appendix A.3):



1
1
1
1
P U − E (U ) ≥ η ≥ √ exp −2η 2 ` − √ .
`
`
7η `
`

(8)

• If P[Ui = 1] = 1/2 for all i, then for all 0 ≤ η ≤ 1/8 such that η` is an integer4 (seeAppendix A.4):


1
1
1
2
P U − E(U ) ≥ η ≥ e−16η ` .
(9)
`
`
5
4. For notational simplicity we omit the floors/ceilings implicit in the use of this bound.

7Helmbold and Long

• A consequence of Slud’s Inequality (1977) gives the following (see Appendix A.5). If
0 ≤ η ≤ 1/5 and P[Ui = 1] = 1/2 + η for all i then:


1
1
2
P U < 1/2 ≥ e−5η ` .
(10)`4Note that the constants in the above bounds were chosen to be simple and illustrative,
rather than the best possible.

3. The accuracy of models containing relevant and irrelevant variables
In this section we analyze the accuracy of the models (hypotheses) produced by the algorithms in Section 4. Each example is represented by a vector of N binary variables and aclass designation. We use the following generative model:• a random class designation from {0, 1} is chosen, with both classes equally likely, then• each of K relevant variables are equal to the class designation with probability 1/2+γ(or with probability 1/2 − γ), and• the remaining N − K irrelevant variables are equal to the class label with probability
1/2;• all variables are conditionally independent given the class designation.
Which variables are relevant and whether each one is positively or negatively correlatedwith the class designations are chosen arbitrarily ahead of time.
A feature is either a variable or its complement. The 2(N − K) irrelevant features
come from the irrelevant variables, the K relevant features agree with the class labelswith probability 1/2 + γ, and the K misleading features agree with the class labels withprobability 1/2 − γ.
We now consider models M predicting with a majority vote over a subset of the features.
We use n for the total number of features in model M, k for the number of relevant features,and ` for the number of misleading features (leaving n − k − ` irrelevant features). Since
the votes of a variable and its negation “cancel out,” we assume without loss of generality
defthat models include at most one feature for each variable. Recall that [z]+ = max{z, 0}.
Theorem 1 Let M be a majority vote of n features, k of which are relevant and ` of which
are misleadingn − k −` are irrelevant). The probability that M predicts incorrectly is (and−2γ 2 [k − `]2+
at most exp.
nProof: If ` ≥ k then the exponent is 0 and the bound trivially holds.
Suppose k > `. Model M predicts incorrectly only when at most half of its features arecorrect. The expected fraction of correct voters is 1/2 + γ(k−`)
n , so, for M’s prediction to beincorrect, the fraction of correct voters must be at least γ(k − `)/n less than its expectation.
Applying (4), this probability is at most
−2γ 2 (k − `)2
exp
.
n
8

Necessity of Irrelevant Variables


The next corollary shows that even models where most of the features are irrelevant canbe highly accurate.
√
Corollary 2 If γ is a constant, k − ` = ω( n) and k = o(n), then the accuracy of themodel approaches 100% while its fraction of irrelevant variables approaches 1 (as n → ∞).
For example, the conditions of Corollary 2 are satisfied when γ = 1/4, k = 2n2/3 and` = n2/3 .

4. Learning
We now consider the problem of learning a model M from data. We assume that thealgorithm receives m i.i.d. examples generated as described in Section 3. One test example
is independently generated from the same distribution, and we evaluate the algorithm’s
expected error : the probability over training set and test example that its model makes anincorrect prediction on the test example (the “prediction model” of Haussler et al. (1994)).
We define Mβ to be the majority vote5 of all features that equal the class label on atleast 1/2 + β of the training examples. To keep the analysis as clean as possible, our resultsin this section apply to algorithms that chose β as a function of the number of features N ,the number of relevant features K, the edge of the relevant features γ, and training set size
m, and then predict with Mβ . Note that this includes the algorithm that always choses
β = 0 regardless of N , K, γ and m.
Recall that asymptotic notation will concern the case in which γ is small, Kγ is large,
and N/K is large.
This section proves two theorems bounding the expected error rates of learned models.
One can compare these bounds with a similar bound on the Bayes Optimal predictor that“knows” which features are relevant. This Bayes Optimal predictor for our generative model2
is a majority vote of the K relevant features, and has an error rate bounded by e−2γ K (abound as tight as the Hoeffding bound).
Theorem 3 If 0 ≤ β ≤ γ, then the expected error rate of Mβ is at most!!
2
[1 − 8e−2(γ−β) m − γ]2+2
(1 + o(1)) exp −2γ K.
1 + 8(N/K)e−2β 2 m + γ
Our proof of Theorem 3 starts with lemmas bounding the number of misleading, irrelevant, and relevant features in Mβ . These lemmas use a quantity δ > 0 that will be
determined later in the analysis.
Lemma 4 With probability at least 1 − δ, the number of misleading features in Mβ is at2
most 4Ke−2(γ+β) m + 3 ln(1/δ).
Proof: For a particular misleading feature to be included in Mβ , Algorithm A must overestimate the probability that misleading feature equals the class label by at least β + γ.
5. If Mβ is empty or the vote is tied then any default prediction, such as 1, will do.

9Helmbold and Long

2

Applying (4), this happens with probability at most e−2(β+γ) m , so the expected number
2of misleading features in Mβ is at most Ke−2(β+γ) m . Since each misleading feature is as2
sociated with a different independent variable, we can apply (7) with E(U ) ≤ Ke−2(β+γ) m
to get the desired result.
Lemma 5 With probability at least 1 − 2δ, the number of irrelevant features in Mβ is at2
most 8N e−2β m + 6 ln(1/δ).
Proof: For a particular positive irrelevant feature to be included in Mβ , Algorithm A mustoverestimate the probability that the positive irrelevant feature equals the class label by
2
β. Applying (4), this happens with probability at most e−2β m , so the expected number of2
irrelevant positive features in Mβ is at most (N − K)e−2β m .
All of the events that variables agree with the label, for various variables, and various
examples, are independent. So the events that various irrelevant variables are included in2
Mβ are independent. Applying (7) with E(U ) = (N −K)e−2β m gives that, with probability
2
at least 1 − δ, the number of irrelevant positive features in Mβ is at most 4(N − K)e−2β m .
A symmetric analysis establishes the same bound on the number of negative irrelevant
features in Mβ . Adding these up completes the proof.
Lemma 6 With probability at least 1 − δ, the number of relevant features in Mβ is at least2
K − 4Ke−2(γ−β) m − 3 ln(1/δ).
Proof: For a particular relevant feature to be excluded from Mβ , Algorithm A must
underestimate the probability that the relevant feature equals the class label by at least2γ − β. Applying (4), this happens with probability at most e−2(γ−β) m , so the expected2
number of relevant variables excluded from Mβ is at most Ke−2(γ−β) m . Applying (7) asin the preceding two lemmas completes the proof.
Lemma 7 The probability that Mβ makes an error is at mosthi2 2−2γ 2 K − 8Ke−2(γ−β) m − 6 ln(1/δ)

+
exp 
 + 4δ.
K + 8N e−2β 2 m + 6 ln(1/δ)


for any δ > 0 and 0 ≤ β ≤ γ.
Proof: The bounds of Lemmas 4, 5, and 6 simultaneously hold with probability at least
1 − 4δ. Thus the error probability of Mβ is at most 4δ plus the probability of error giventhat all three bounds hold. Plugging the three bounds into Theorem 1, (and over-estimating
the number n of variables in the model with K plus the bound of Lemma 5 on the numberof irrelevant variables) gives a bound on Mβ ’s error probability of
h
i2 
2
2
−2γ 2 (K − 4Ke−2(γ−β) m − 3 ln(1/δ)) − (4Ke−2(γ+β) m + 3 ln(1/δ))

+
exp 

2m
−2β
K + 8N e+ 6 ln(1/δ)


10

(11)

Necessity of Irrelevant Variables

when all three bounds hold. Under-approximating (γ + β)2 with (γ − β)2 and simplifying
yields:


−2γ 2

h


(11) ≤ exp i2 2K − 8Ke−2(γ−β) m − 6 ln(1/δ)

K + 8N e−2β 2 m + 6 ln(1/δ)+Adding 4δ completes the proof.

.


We are now ready to prove Theorem 3.
Proof (of Theorem 3): UsingγKδ = exp −6
in Lemma 7 bounds the probability that Mβ makes a mistake by
h
i2 
2


−2γ 2 K − 8Ke−2(γ−β) m − γK
γK

+
+
4
exp
−
exp 

6
K + 8N e−2β 2 m + γK


h
i2 
2


−2γ 2 K 1 − 8e−2(γ−β) m − γγK+< exp . (12)
 + 4 exp −−2β 2 m + γ
6
1 + 8NK e


2

The first term is at least e−2γ K , and




γK
2
4 exp −= o e−2γ K
6as γ → 0 and γK → ∞, so (12) implies the boundhi2 2−2γ 2 K 1 − 8e−2(γ−β) m − γ+(1 + o(1)) exp 
−2β 2 m + γ
1 + 8NeK

as desired.

The following theorem bounds the error in terms of just K, N , and γ when m issufficiently large.
Theorem 8 Suppose algorithm A produces models Mβ where 0 ≤ β ≤ cγ for a constantc ∈ [0, 1).
2• Then there is a constant b (depending only on c) such that whenever m ≥ b/γ the22error of A’s model is at most (1 + o(1)) exp − γ NK .

11

Helmbold and Long

• If m = ω(1/γ 2 ) then the error of A’s model is at most (1 + o(1)) exp

−(2−o(1))γ 2 K 2N.

Proof Combining Lemmas 4 and 6 with the upper bound of N on the number of featuresin Mβ as in Lemma 7’s proof gives the following error bound on Mβ

h
i2 
2
−2γ 2 K − 8Ke−2(γ−β) m − 6 ln(1/δ)

+
exp 
 + 2δ
N
for any δ > 0. SettingγKδ = exp −6
and continuing as in the proof of Theorem 3 gives the bound

h

i2 
2m
2
2
−2(γ−β)−2γ K 1 − 2 4e+γ+
(1 + o(1)) exp 
.
N

(13)

For the first part of the theorem, it suffices to show that the [· · · ]2+ term is at least 1/2.
Recalling that our analysis is for small γ, the term inside the [· · · ]+ of (13) is at least2 2

1 − 8e−2(1−c) γ m − o(1).
Whenm≥ln (32),2(1 − c)2 γ 2(14)this term is at least 3/4 − o(1), and thus its square is at least 1/2 for small enough γ,
completing the proof of the first part of the theorem.
To see the second part of the theorem, since m ∈ ω(1/γ 2 ), the term of (13) inside the[· · · ]+ is 1 − o(1).
By examining inequality (14), we see that the constant b in Theorem 8 can be set toln(32)/2(1 − c)2 .
2Lemma 9 The expected number of irrelevant variables in Mβ is at least (N − K)e−16β m .
Proof Follows from inequality (9).

Corollary 10 If K, N , and m are functions of γ such thatγ → 0,
K 2 /N ∈ ω(ln(1/γ)/γ 2 ),K = o(N ) andm = 2 ln(32)/γ 2
12Necessity of Irrelevant Variables

then if an algorithm outputs Mβ using a β in [0, γ/2], it has an error that decreases superpolynomially (in γ), while the expected fraction of irrelevant variables in the model goes to1.
Note that Theorem 8 and Corollary 10 include non-trivial error bounds on the modelM0 that votes all N variables (for odd sample size m).

5. Lower boundHere we show that any algorithm with an error guarantee like Theorem 8 must include
many irrelevant features in its model. The preliminary version of this paper (Helmbold andLong, 2011) contains a related lower bound for algorithms that choose β as a function of
N , K, m, and γ, and predict with Mβ . Here we present a more general lower bound thatapplies to algorithms outputting arbitrary hypotheses. This includes algorithms that use
weighted voting (perhaps with L1 regularization). In this section we• set the number of features N , number of relevant features K, and sample size m as afunctions of γ in such a way that Corollary 10 applies, and• prove a constant lower bound for these combinations of values that holds for “exclusive” algorithms (defined below) when γ is small enough.
Thus, in this situation, “inclusive” algorithms relying on many irrelevant variables haveerror rates going to zero while every “exclusive” algorithm has an error rate bounded below
by a constant.
The proofs in this section assume that all relevant variables are positively correlatedwith the class designation, so each relevant variable agrees with the class designation withprobability 1/2 + γ. Although not essential for the results, this assumption simplifies thedefinitions and notation6 . We also set m = 2 ln(32)/γ 2 . This satisfies the assumption ofTheorem 8 when β ≤ γ/2 (see Inequality (14)).
Definition 11 We say a classifier f includes a variable xi if there is an input (x1 , ..., xN )such thatf (x1 , ..., xi−1 , xi , xi+1 , ..., xN ) 6= f (x1 , ..., xi−1 , 1 − xi , xi+1 , ..., xN ).
Let V (f ) be the set of variables included in f .
For a training set S, we will refer to the classifier output by algorithm A on S as A(S).
Let R be the set of relevant variables.
Definition 12 We say that an algorithm A is λ-exclusive7 if for every positive N , K, γ,
and m, the expected fraction of thevariables included in its hypothesis that are relevant is|V (A(S)) ∩ R|
≥ λ.
at least λ, i.e. E|V (A(S))|
6. The assumption that each relevant variable agrees with the class label with probability 1/2 + γ gives a
special case of the generative model described in Section 4, so the lower bounds proven here also apply
to that more general setting.
7. The proceedings version of this paper (Helmbold and Long, 2011) used a different definition of λ-exclusive.

13

Helmbold and Long

Our main lower bound theorem is the following.
Theorem 13 If


1
1/3
exp
ln(1/γ)γ2N = K exp ln(1/γ)1/4K=m=

2 ln(32)γ2then for any constant λ > 0 and any λ-exclusive algorithm A, the error rate of A is lower
bounded by λ/4 − o(1) as γ goes to 0.
Notice that this theorem provides a sharp contrast to Corollary 10. Corollary 10 showsthat inclusive A using models Mβ for any 0 ≤ β ≤ γ/2 have error rates that goes to zerosuper-polynomially fast (in 1/γ) under the assumptions of Theorem 13.
The values of K and N in Theorem 13 are chosen to make the proof convenient, butother values would work. For example, decreasing K and/or increasing N would makethe lower bound part of Theorem 13 easier to prove. There is some slack to do so while
continuing to ensure that the upper bound of Corollary 10 goes to 0.
As the correlation of variables with the label over the sample plays a central role in our
analysis, we will use the following definition.
Definition 14 If a variable agrees with the class label on 1/2 + η of the training set thenit has (empirical) edge η.
The proof of Theorem 13 uses a critical value of β, namely β ∗ = γ ln(N/K)/10 ln(32),with the property that both:
E (|Mβ ∗ ∩ R|)→0
E (|Mβ ∗ |)(15)

E (|Mβ ∗ ∩ R|) ∈ o(1/γ 2 )(16)

as γ → 0.
Intuitively, (15) means that any algorithm that uses most of the variables having empirical edge at least β ∗ cannot be λ-exclusive. On the other hand, (16) implies that if
the algorithm restricts itself to variables with empirical edges greater than β ∗ then it does
not include enough relevant variables to be accurate. The proof must show that arbitraryalgorithms frequently include either too many irrelevant variables to be λ-exclusive or too
few relevant ones to be accurate. See Figure 3 for some useful facts about γ, m, and β ∗ .
To prove the lower bound, borrowing a technique from Ehrenfeucht et al. (1989), we
will assume that the K relevant variables are randomly selected from the N variables, andlower bound the error with respect to this random choice, along with the training and test
data. This will then imply that, for each algorithm, there will be a choice of the K relevant
variables giving the same lower bound with respect only to the random choice of the training
and test data. We will always use relevant variables that are positively associated with theclass label, agreeing with it with probability 1/2 + γ.
14

Necessity of Irrelevant Variablesb = 2 ln(32)m=b
2 ln(32)
=
2
γ
γ2

β∗ =

γ ln(1/γ)1/4
γ ln(N/K)=
5b
10 ln(32)

Figure 3: Some useful facts relating b, γ, m and β ∗ under the assumptions of Theorem 13.

Proof [of Theorem 13] Fix any learning algorithm A, and let A(S) be the hypothesis
produced by A from sample S. Let n(S) be the number of variables included in A(S) andlet β(S) be the n(S)’th largest empirical (w.r.t. S) edge of a variable.
Let qγ be the probability that β(S) ≥ β ∗ = γ ln(N/K)/10 ln(32). We will show in
Section 5.2 that if A is λ-exclusive then λ ≤ qγ + o(1) (as γ goes to 0). We will also showin Section 5.3 that the expected error of A is at least qγ /4 − o(1) as γ goes to 0. Therefore
any λ-exclusive algorithm A has an expected error rate at least λ/4 − o(1) as γ goes to 0.
Before attacking the two parts of the proof alluded to above, we need a subsection
providing some basic results about relevant variables and optimal algorithms.
5.1 Relevant Variables and Good Hypotheses
This section proves some useful facts about relevant variables and good hypotheses. The
first lemma is a lower bound on the accuracy of a model in terms of the number of relevant
variables.
Lemma 15 If γ ∈ [0, 1/5] then any classifier using k relevant variables has an error prob2
ability at least 14 e−5γ k .
Proof: The usual Naive Bayes calculation (see Duda et al., 2000) implies that the optimalclassifier over a certain set V of variables is a majority vote over V ∩ R. Applying the lower
tail bound (10) then completes the proof.

Our next lemma shows that, given a sample, the probability that a variable is relevant(positively correlated with the class label) is monotonically increasing in its empirical edge.
Lemma 16 For two variables xi and xj , and any training set S of m examples,• P[xi relevant | S] > P[xj relevant | S] if and only if the empirical edge of xi in S isgreater than the empirical edge of xj in S, and• P[xi relevant | S] = P[xj relevant | S] if and only if the empirical edge of xi in S isequal to the empirical edge of xj in S.
15

Helmbold and Long

Proof Since the random choice of R does not effect that marginal distribution over thelabels, we can generate S by picking the labels for all the examples first, then R, andfinally the values of the variables on all the examples. Thus if we can prove the lemma
after conditioning on the values of the class labels, then scaling all of the probabilities by
2−m would complete the proof. So, let us fix the values of the class labels, and evaluate
probabilities only with respect to the random choice of the relevant variables R, and thevalues of the variables.
Let∆ = P[xi ∈ R|S] − P[xj ∈ R|S] .
First, by subtracting off the probabilities that both variables are relevant, we have
∆ = P xi ∈ R, xj 6∈ R S − P xi 6∈ R, xj ∈ R S .
Let ONE be the event that exactly one of xi or xj is relevant. Then
∆ = ( P xi ∈ R, xj 6∈ R S, ONE − P xi 6∈ R, xj ∈ R S, ONE ) P[ONE] .
So ∆ > 0 if and only if




def
∆0 = P xi ∈ R, xj 6∈ R S, ONE − P xi 6∈ R, xj ∈ R S, ONE > 0(and similarly for ∆ = 0 if and only if ∆0 = 0). If Q is the distribution obtained byconditioning on ONE, then
∆0 = Q xi ∈ R, xj 6∈ R S − Q xi 6∈ R, xj ∈ R S .
Let Si be the values of variable i in S, and define Sj similarly for variable j. Let S 0
be the values of the other variables. Since we have already conditioned on the labels, afteralso conditioning on ONE (i.e., under the distribution Q), the pair (Si , Sj ) is independentof S 0 . For each Si we have P[Si | xi 6∈ R] = Q[Si | xi 6∈ R]. Furthermore, by symmetry,
 1



Q xi ∈ R, xj 6∈ R S 0 = Q xi 6∈ R, xj ∈ R S 0 = .
2Thus, by using Bayes’ Rule on each term, we have
∆0 = Q xi ∈ R, xj 6∈ R Si , Sj , S 0 − Q xi 6∈ R, xj ∈ R Si , Sj , S 0Q Si , Sj xi ∈ R, xj 6∈ R, S 0 − Q Si , Sj xi 6∈ R, xj ∈ R, S 0=
2 Q[Si , Sj |S 0 ](1/2 + γ)mi (1/2 − γ)m−mi − (1/2 + γ)mj (1/2 − γ)m−mj=,
2m+1 Q[Si , Sj ]where mi and mj are the numbers of times that variables xi and xj agree with the label insample S. The proof concludes by observing that ∆0 is positive exactly when mi > mj andzero exactly when mi = mj .
Because, in this lower bound proof, relevant variables are always positively associatedwith the class label, we will use a variant of Mβ which only considers positive features.
16

Necessity of Irrelevant Variables

Definition 17 Let Vβ be a vote over the variables with empirical edge at least β.
When there is no chance of confusion, we will refer to the set of variables in Vβ also as Vβ(rather than V (Vβ )).
We now establish lower bounds on the probability of variables being included in Vβ (hereβ can be a function of γ, but does not depend on the particular sample S).
Lemma 18 If γ ≤ 1/8 and β ≥ 0 then the probability that a given variable has empiricaledge at least β is at least1
exp −16β 2 m .
5
If in addition m ≥ 1/β 2 , then the probability that a given variable has empirical edge atleast β is at least
1
1√ exp −2β 2 m − √ .
7β mm
Proof: Since relevant variables agree with the class label with probability 1/2 + γ, theprobability that a relevant variable has empirical edge at least β is lower bounded by theprobability that an irrelevant variable has empirical edge at least β. An irrelevant variable
has empirical edge at least β only when it agrees with the class on 1/2 + β of the sample.
Applying Bound (9), this happens with probability at least 51 exp −16β 2 m . The second
part uses Bound (8) instead of (9).

We now upper bound the probability of a relevant variable being included in Vβ , again
for β that does not depend on S.
Lemma 19 If β ≥ γ, the probability that a given relevant variable has empirical edge at2
least β is at most e−2(β−γ) m .
Proof: Use (4) to bound the probability that a relevant feature agrees with the class label
β − γ more often than its expected fraction of times.

5.2 Bounding λ-Exclusiveness
Recall that n(S) is the number of variables used by A(S), and β(S) is the edge of thevariable whose rank, when the variables are ordered by their empirical edges, is n(S). We
will show that: if A(S) is λ-exclusive, then there is reasonable probability that β(S) is atleast the critical value β ∗ = γ ln(N/K)/5b. Specifically, if A is λ-exclusive, then, for any
small enough γ, we have P[β(S) ≥ β ∗ ] > λ/2.
Suppose, given the training set S, the variables are sorted in decreasing order of empiricaledge (breaking ties arbitrarily, say using the variable index). Let VS,k consist of the first kvariables in this sorted order, the “top k” variables.
Since for each sample S and each variable xi , the probability P xi relevantSdecreases|VS,k ∩ R|
as the empirical edge of xi decreases (Lemma 16), the expectation E
S is|VS,k |
non-increasing with k.
17Helmbold and Long

Furthermore, Lemma 16 also implies that for each sample S, we haveE

|V (A(S)) ∩ R|
S
|V (A(S))|




≤E


|VS,n(S) ∩ R|
S .
|VS,n(S) |Therefore, by averaging over samples, for each γ we haveE

|V (A(S)) ∩ R|
|V (A(S))|




≤E

|VS,n(S) ∩ R|
|VS,n(S) |


.

(17)

Note that the numerators in the expectations are never greater than the denominators.
We will next give upper bounds on |Vβ ∗ ∩ R| and lower bounds on |Vβ ∗ | that each hold withprobability 1 − γ.
The next step is a high-confidence upper bound on |Vβ ∗ ∩ R|. From Lemma 19, theprobability that a particular relevant variable is in Vβ ∗ is at most (recall that m = b/γ 2 )
∗

∗

2

2

e−2(β −γ) m = e−2b(β /γ−1)= exp −2b

= exp
< exp

ln(1/γ)1/4
5b

!2 
−1



!
−2 ln(1/γ)1/2 4 ln(1/γ)1/4
+
− 2b
25b
5
!
−2 ln(1/γ)1/2 4 ln(1/γ)1/4
+
.
25b
5



1/2
4 ln(1/γ)1/4
be this upper bound, and note that prel drops
Let prel = exp −2 ln(1/γ)+
25b5
to 0 as γ goes to 0, but a rate slower than γ  for any . The number of relevant variables
in Vβ ∗ has a binomial distribution with parameters K and p where p < prel . The standard
deviation of this distribution isln(1/γ)1/3 √
exp
prel
p
p
2
σ = Kp(1 − p) < Kp <.
(18)
γUsing the Chebyshev bound,
P[|X − E(X)| > aσ] ≤

1
a2

(19)

√
with a = 1/ γ gives thatσ
P |Vβ ∗ ∩ R| − Kp > √
≤ γ
γ


σ
P |Vβ ∗ ∩ R| > Kprel + √
≤ γ.
γ
18

(20)

Necessity of Irrelevant Variables√√√
Since σ < Kp < Kprel by (18), we have σ Kprel < Kprel . Substituting the valuesof K and prel into the square-root yields
exp
Kprel > σ ×√> σ/ γ,ln(1/γ)1/3
2



exp



1/4
− ln(1/γ)1/2+ 2 ln(1/γ)
25b
5



γ

for small enough γ. Combining with (20), we get that
P[|Vβ ∗ ∩ R| > 2Kprel ] ≤ γ(21)holds for small enough γ.
Using similar reasoning, we now obtain a lower bound on the expected number of variables in Vβ ∗ . Lemma 18 shows that, for each variable, the probability of the variable having
empirical edge β ∗ is at least

7β

1
√
∗

!
√

1/2
1
5
b
ln(1/γ)γ
exp −2β ∗ 2 m − √ =exp −2
−√
1/4
25b
m
m
7 ln(1/γ)b!
√bln(1/γ)1/2
>
exp
−2
25b
2 ln(1/γ)1/4
for sufficiently small γ. Since the empirical edges of different variables are independent, theprobability that at least n variables have empirical edge at least β ∗ is lower bounded by theprobability of at least n successes from the binomial distribution with parameters N andpirrel where!
√bln(1/γ)1/2.
pirrel =exp −225b
2 ln(1/γ)1/4
If, now, we p
define σ to be the standard
deviation of this binomial distribution, then, like√before, σ = N pirrel (1 − pirrel ) < N pirrel , andN pirrel /2 > σ=pN pirrel /2

σ exp((1/2)(ln(1/γ)1/4 + ln(1/γ)1/3 ))ln(1/γ)1/2
b1/4
×
×√
exp −
2
γ
25b
2 ln(1/γ)1/8!

√
so that, for small enough γ, N pirrel /2 > σ/ γ. Therefore applying the Chebyshev bound (19)√with a = 1/ γ gives (for sufficiently small γ)
N pirrel√≤ P[|Vβ ∗ | < N pirrel − σ/ γ] < γ.
P |Vβ ∗ | <2
Recall thatqγ = P[β(S) ≥ β ∗ ] = P[n(S) ≤ |Vβ ∗ |] .
19

(22)

,

Helmbold and Long

If A is λ-exclusive then, using (17), we have|VS,n(S) ∩ R|
|V (A(S)) ∩ R|)≤E
λ≤E|V (A(S))||VS,n(S) ||VS,n(S) ∩ R|
≤ (1 − qγ )E|Vβ ∗ | < n(S) + qγ
|VS,n(S) ||Vβ ∗ ∩ R|
≤ (1 − qγ )E|Vβ ∗ | < n(S) + qγ
|Vβ ∗ |

2Kprel≤ (1 − qγ )+ 2γ + qγ
N pirrel /2
where we use the upper and lower bounds from Equations (21) and (22) that each hold withprobability 1 − γ. Note that the ratio!
−2 ln(1/γ)1/2 4 ln(1/γ)1/4
exp
+
25b
5
2Kprel
!
≤
√
1/3
1/4
N pirrel /2
eln(1/γ) eln(1/γ)
bln(1/γ)1/2
exp −24γ 225bln(1/γ)1/4
!
1/2
1/4
−2
ln(1/γ)4ln(1/γ)8 ln(1/γ)1/4 exp
+
25b
5
!
=
√ ln(1/γ)1/4
ln(1/γ)1/2beexp −225b!
− ln(1/γ)1/4
8 ln(1/γ)1/4 exp
5√=bwhich goes to 0 as γ goes to 0. Therefore,|V (A(S)) ∩ R|)
λ≤E≤ qγ + o(1)|V (A(S))|
1/3eln(1/γ)2γ2which implies that,qγ = P[β(S) ≥ β ∗ ] ≥ λ − o(1)as γ goes to 0.
5.3 Large Error
Call a variable good if it is relevant and its empirical edge is at least β ∗ in the sample. Let
p be the probability that a relevant variable is good. Thus the number of good variables
is binomially distributed with parameters K and p. We have that the expected number ofgood variables is pK and the variance is Kp(1 − p) < Kp. By Chebyshev’s inequality, we
have
h
h
i
p
p i
1
P # good vars ≥ Kp + a Kp ≤ P # good vars ≥ Kp + a Kp(1 − p) ≤ 2 ,
(23)
a
20

Necessity of Irrelevant Variables

and setting a =√Kp, this gives
P[# good vars ≥ 2Kp] ≤
∗

1
.
Kp

1/4 /5b−1 2

By Lemma 19, Kp ≤ Ke−2(β −γ) m = Ke−2b(ln(1/γ)
ln(Kp) ≤ ln K − 2b

(24)

2

ln(1/γ)1/2 2 ln(1/γ)1/4
−
+1
25b2
5b

ln(Kp) ≤ 2 ln(1/γ) + ln(1/γ)1/3 − 2b

) , so!

!
ln(1/γ)1/2 2 ln(1/γ)1/4
−
+1 .
25b2
5b

So for small enough γ,ln(Kp) ≤ 2 ln(1/γ) −ln(1/γ)1/2
25b

and thus Kp ∈ o(1/γ 2 ).
So if Kp > 1/γ, then with probability at least 1 − γ, there arep
less than 2Kp ∈ o(1/γ 2 )good variables. On the other hand, if Kp < 1/γ, then, setting a = 1/γ in bound (23) givesthat the probability that there are more than 2/γ good variables is atmost γ. So in eithercase the probability that there are more than γ22 exp − ln(1/γ)1/2 /25b good variables is at
most γ (for small enough γ).
So if P[β(S) ≥ β ∗ ] ≥ qγ , then with probability
 at least qγ − γ algorithm A is using ahypothesis with at most γ22 exp − ln(1/γ)1/2 /25b relevant variables. Applying Lemma 15
yields the following lower bound on the probability of error:1(qγ − γ) exp −10 exp − ln(1/γ)1/2 /25b .
(25)
4
Since the limit of (25) for small γ is qγ /4, this completes the proof of Theorem 13.

6. Relaxations of some assumptions
To keep the analysis clean, and facilitate the interpretation of the results, we have analyzed
an idealized model. In this section, we briefly consider the consequences of some relaxationsof our assumptions.
6.1 Conditionally dependent variables
Theorem 1 can be generalized to the case in which there is limited dependence among thevariables, after conditioning on the class designation, in a variety of ways. For example,
suppose that there is a degree-r graph G whose nodes are variables, and such that, conditioned on the label, each variable is independent of all variables not connected to it byan edge in G. Assume that k variables agree with the label with probability 1/2 + γ, andthe n − k agree with the label with probability 1/2. Let us say that a source like thishas r-local dependence. Then applying a Chernoff-Hoeffding bound for such sets of random2 k2variables due to Pemmaraju (2001), if r ≤ n/2, one gets a bound of c(r + 1) exp −2γn(r+1)
the probability of error.
21

Helmbold and Long

6.2 Variables with different strengths
We have previously assumed that all relevant variables are equally strongly associated withthe class label. Our analysis is easily generalized to the situation when the strengths ofassociations fall in an interval [γmin , γmax ]. Thus relevant variables agree with the classlabel with probability at least 1/2 + γmin and misleading variables agree with the classlabel with probability at least 1/2 − γmax . Although a sophisticated analysis would takeeach variable’s degree of association into account, it is possible to leverage our previous
analysis with a simpler approach. Using the 1/2 + γmin and 1/2 − γmax underestimates on
the probability that relevant variables and misleading variables agree with the class label
leads to an analog of Theorem 1. This analog says that models voting n variables, k ofwhich are relevant and ` of which are misleading, have error probabilities bounded by
−2[γmin k − γmax `]2+exp.
n
We can also use the upper and lower bounds on association to get high-confidencebounds (like those of Lemmas 4 and 6) on the numbers of relevant and misleading featuresin models Mβ . This leads to an analog of Theorem 3 bounding the expected error rate of
Mβ by

h
i2 
−2(γmin −β)2 m − γ
2 K 1 − 4(1 + γ−2γminmax /γmin )emin+(1 + o(1)) exp 
8N −2β 2 m
1+ K e+ γminwhen 0 ≤ β ≤ γ and γmax ∈ o(1). Note that γ in Theorem 3 is replaced by γmin here,and γmax only appears in the 4(1 + γmax /γmin ) factor (which replaces an “8” in the original
theorem).
Continuing to mimic our previous analysis gives analogs to Theorem 8 and Corollary 10.
These analogs imply that if γmax /γmin is bounded then algorithms using small β perform
well in the same limiting situations used in Section 5 to bound the effectiveness of exclusive
algorithms.
A more sophisticated analysis keeping better track of the degree of association between
relevant variables and the class label may produce better bounds. In addition, if the variables have varying strengths then it makes sense to consider classifiers that assign different
voting weights to the variables based on their estimated strength of association with theclass label. An analysis that takes account of these issues is a potentially interesting subject
for further research.

7. Conclusions
We analyzed learning when there are few examples, a small fraction of the variables are
relevant, and the relevant variables are only weakly correlated with the class label. In
this situation, algorithms that produce hypotheses consisting predominately of irrelevant
variables can be highly accurate (with error rates going to 0). Furthermore, this inclusionof many irrelevant variables is essential. Any algorithm limiting the expected fraction ofirrelevant variables in its hypotheses has an error rate bounded below by a constant. This
22

Necessity of Irrelevant Variables

is in stark contrast with many feature selection heuristics that limit the number of features
to a small multiple of the number of examples, or that limit the classifier to use variables
that pass stringent statistical tests of association with the class label.
These results have two implications on the practice of machine learning. First, theyshow that the engineering practice of producing models that include enormous numbers ofvariables is sometimes justified. Second, they run counter to the intuitively appealing viewthat accurate class prediction “validates” the variables used by the predictor.

Acknowledgements
We thank Aravind Srinivasan for his help.

Appendix A. AppendicesA.1 Proof of (5) and (6)Equation 4.1 from (Motwani and Raghavan, 1995) is
P[U > (1 + η)E(U )] <eη
(1 + η)1+ηE(U )(26)

and holds for independent 0-1 valued Ui ’s each with (possibly different) probabilities pi =P (Ui = 1) where 0 < pi < 1 and η > 0. Taking the logarithm of the RHS, we getln(RHS) = E(U ) (η − (1 + η) ln(1 + η))(27)< E(U ) (η + 1 − (1 + η) ln(1 + η))= −E(U )(η + 1)(ln(1 + η) − 1),which implies (5). From (26), when 0 ≤ η ≤ 4 (since η − (1 + η) ln(1 + η) < −η 2 /4 there),
P[U > (1 + η)E(U )] < exp −η 2 E(U )/4 showing (6).
A.2 Proof of (7)Using (5) with η = 3 + 3 ln(1/δ)/E(U ) givesP[U > 4E(U ) + 3 ln(1/δ)] < exp −(4E(U ) + 3 ln δ) ln 4< exp −(3 ln(1/δ) lne< exp (− ln(1/δ)) = δ

4 + 3 ln(1/δ)/E(U )eusing the fact that ln(4/e) ≈ 0.38 > 1/3.
A.3 Proof of (8)The following is a straightforward consequence of the Berry-Esseen inequality.
23Helmbold and Long

Lemma 20 ((see DasGupta, 2008, Theorem 11.1)) Under the assumptions of Section 2 with each P[Ui = 1] = 1/2, let:Ti = 2(Ui − 1/2),
r
`
1 X
T =
Ti , and`i=1

Z be a standard normal random variable.
1
Then for all η, we have P[T > η] − P[Z > η] ≤ √ .
`Lemma 21 ((Feller, 1968, Chapter VII, section 1)) If Z is a standard normal random variable and x > 0, then


 
1
1
1
1
1
2
2
√
− 3 e−x /2 < P[Z > x] < √e−x /2 .
x
x
x
2π
2π
P
Now, to prove (8), let M = 1` `i=1 (Ui − 12 ) and let Z be a standard normal randomvariable. Then Lemma 20 implies that, for all κh √i
1
P 2 `M > κ − P[Z > κ] ≤ √ .
`√Using κ = 2η `,
h
√ i
1
(28)
P[M > η] ≥ P Z > 2η ` − √ .
`Applying Lemma 21, we get

3 !
h
√ i
1
1
1
2
√ −
√
P Z > 2η ` ≥ √e−2η ` .
2π 2η `
2η `Since ` ≥ 1/η 2 , we get


√ i
1
1 1
1
2
√ e−2η `P Z > 2η ` ≥ √−2π 2 8 η `1 −2η2 `
√ e
≥
.
7η `
h

Combining with (28) completes the proof of (8).



A.4 Proof of (9)We follow the proof of Proposition 7.3.2 in (Matoušek and Vondrak, 2011, Page 46).
Lemma
P 22 For n even, let U1 , . . . , Un be i.i.d. RVs with P[U1 = 0] = P[U1 = 1] = 1/2 andU = ni=1 . Then for integer t ∈ [0, n8 ],
h
i 1
n
2
P U ≥ + t ≥ e−16t /n .
2
524

Necessity of Irrelevant Variables

Proof Let integer m = n/2.
−2m

P[U ≥ m + t] = 2


m 
X
2m

−2m

≥2

2t−1
X
j=t

−2m

=2

(29)

m+j

j=t

2m
m+j


(30)

2t−1
X
j=t


2m
m
m−1
m−j+1
·
·
···
m+j m+j−1
m+1m

2t−1 j 
√1 XY
j≥ 22m /2 musing 2m
≥ √
1−
m
m+1
2 m
j=t i=1


2t 2t
t
1−
≥ √
m
2 m
t
2
since 1 − x ≥ e−2x for 0 ≤ x ≤ 1/2.
≥ √ e−8t /m
2 m

(31)

(32)

(33)
(34)

√
2
For t ≥ 12 m, the last expression is at least 14 e−16t /n .
√1√Note that P[U = m] = 2−2m 2mm ≤ 1/ πm. Thus for 0 ≤ t < 2 m, we have1
− t P[U = m]
2
1 1√
1
≥ −
m√
2 2
πm
1
1
1
1
2
≥ − √ ≈ 0.218 ≥ ≥ e−16 /n
2 2 π
5
5

P[U ≥ m + t] ≥

(35)
(36)
(37)

2

Thus the bound 15 e−16t /n holds for all 0 ≤ t ≤ m/4.

A.5 Proof of (10)The proof of (10) uses the next two lemmas and and follows the proof of Lemma 5.1
in (Anthony and Bartlett, 1999).
Lemma 23 (Slud’s Inequality, (Slud, 1977)) Let B be a binomial (`, p) random variable with p ≤ 1/2. Then for `(1 − p) ≥ j ≥ `p,"#j − `pP[B ≥ j] ≥ P Z ≥ p`p(1 − p)where Z is a standard normal random variable.
Lemma 24 ((see Anthony and Bartlett, 1999, Appendix 1)) If Z is a standard normal and x > 0 thenp1P[Z ≥ x] ≥1 − 1 − e−x2 .
225

Helmbold and Long

Recall that in (10) U the sum of the ` i.i.d. boolean random variables, each of which is 1
with probability 21 +η. Let B be a random variable with the binomial (`, 12 −η) distribution.
1
P U < 1/2 = P[B ≥ `/2]`"`/2 − `(1/2 − η)#≥P N≥p`(1/2 + η)(1/2 − η)
#
"
√
2η `
=P N≥p(1 − 4η 2 )s!

1
4η 2 `
1 − 1 − exp −≥2
1 − 4η 2

1
4η 2 `≥ exp −
4
1 − 4η 2
1≥ exp −5η 2 `4Slud’s Inequality

since 1 −√1 − x > x/2

when η ≤ 1/5

completing the proof of (10).

References
F. Abramovich, Y. Benjamini, D. Donoho, and I. M. Johnstone. Adapting to unknown
sparsity by controlling the false discovery rate. Annals of Statistics, 34:584–653, 2006.
L. Addario-Berry, N. Broutin, L. Devroye, and G. Lugosi. On combinatorial testing problems. The Annals of Statistics, 38(5):3063–3092, 2010.
N. Alon, J. H. Spencer, and P. Erdös. The Probabilistic Method. Wiley, 1992.
D. Angluin and L. Valiant. Fast probabilistic algorithms for Hamiltonion circuits andmatchings. J. Comp. Sys. Sci., 18(2):155–193, 1979.
M. Anthony and P. L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
P. Bickel and E. Levina. Some theory of Fisher’s linear discriminant function, ‘Naive Bayes’,
and some alternatives when there are many more variables than observations. Bernoulli,10(6):989–1010, 2004.
Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
Leo Breiman. Arcing classifiers. The Annals of Statistics, 1998.
P. Bühlmann and B. Yu. Analyzing bagging. Annals of Statistics, 30:927–961, 2002.
A. DasGupta. Asymptotic theory of statistics and probability. Springer, 2008.
26

Necessity of Irrelevant Variables

S. Dasgupta and P. M. Long. Boosting with diverse base classifiers. COLT, 2003.
D. Donoho and J. Jin. Higher criticism for detecting sparse heterogeneous mixtures. Annalsof Statistics, 32:952–994, 2004.
D. Donoho and J. Jin. Asymptotic minimaxity of false discovery rate thresholding for sparse
exponential data. Annals of Statistics, 34, 2006.
D. Donoho and J. Jin. Higher criticism thresholding: optimal feature selection when usefulfeatures and rare and weak. PNAS, 105(39):14790–14795, 2008.
R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification (2nd ed.). Wiley, 2000.
A. Ehrenfeucht, D. Haussler, M. Kearns, and L. G. Valiant. A general lower bound on thenumber of examples needed for learning. Information and Computation, 82(3):247–251,
1989.
J. Fan and Y. Fan. High dimensional classification using features annealed independence
rules. The Annals of Statistics, 36(6):2605Äı̀–2637, 2008.
W. Feller. An introduction to probability theory and its applications. John Wiley & Sons,
1968.
J. Friedman, T. Hastie, and R. Tibshirani. Additive logistic regression: A statistical viewof boosting. The Annals of Statistics, 38(2):337–407, 2000.
D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting {0, 1}-functions on randomly
drawn points. Information and Computation, 115(2):129–161, 1994.
D. P. Helmbold and P. M. Long. On the necessity of irrelevant variables. ICML, 2011.
J. Jin. Impossibility of successful classication when useful features are rare and weak. PNAS,
106(22):8859–8864, 2009.
V. Koltchinskii and D. Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. Annals of Statistics, 30(1), 2002.
J. Matoušek and J. Vondrak. The probabilistic method, 2011. Lecture notes.
N. Meinshausen and J. Rice. Estimating the proportion of false null hypotheses among alarge number of independently tested hypotheses. Annals of Statistics, 34(1):373–393,
2006.
R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifiers: A comparison oflogistic regression and naive bayes. NIPS, 2001.
S. Pemmaraju. Equitable coloring extends Chernoff-Hoeffding bounds. RANDOM, 2001.
D. Pollard. Convergence of Stochastic Processes. Springer Verlag, 1984.
27

Helmbold and Long

J. Quinlan. Bagging, boosting and C4.5. AAAI, 1996.
R. E. Schapire, Y. Freund, P. L. Bartlett, and W. S. Lee. Boosting the margin: A new
explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651–1686, 1998.
E. Slud. Distribution inequalities for the binomial law. Annals of Probability, 5:404–412,
1977.
R. Tibshirani, T. Hastie, B. Narasimhan, and G. Chu. Diagnosis of multiple cancer types
by shrunken centroids of gene expression. PNAS, 99(10):6567–72, 2002.
V. N. Vapnik. Statistical Learning Theory. New York, 1998.
L. Wang, M. Sugiyama, C. Yang, Z. Zhou, and J. Feng. On the margin explanation of
boosting algorithms. COLT, 2008.

28