Generalized Binary Search For Split-Neighborly Problems

Stephen Mussmann
Stanford University

arXiv:1802.09751v1 [] 27 Feb 2018

Abstract
In sequential hypothesis testing, Generalized
Binary Search (GBS) greedily chooses the
test with the highest information gain at each
step. It is known that GBS obtains the gold
standard query cost of O(log n) for problems
satisfying the k-neighborly condition, which
requires any two tests to be connected by a
sequence of tests where neighboring tests disagree on at most k hypotheses. In this paper, we introduce a weaker condition, splitneighborly, which requires that for the set of
hypotheses two neighbors disagree on, any
subset is splittable by some test. For four
problems that are not k-neighborly for any
constant k, we prove that they are splitneighborly, which allows us to obtain the optimal O(log n) worst-case query cost.

1

Introduction

Sequential hypothesis testing (Young & Young, 1998)
aims to find the true hypothesis from a set of hypotheses by performing tests. Some examples are gathering
observations to deduce the location of a hidden object
or labeling data points to infer an underlying classifier. One commonly used algorithm is Generalized Binary Search (GBS), also known as the splitting algorithm, which greedily chooses the test that most evenly
splits the hypothesis version space (Garey & Graham,
1974; Nowak, 2008), or equivalently greedily chooses
the test with the maximal information gain (for binary
tests). Greedy information gain is surprisingly effective in practice and has become the gold standard with
a variety of applications, approximations, and extensions (Settles, 2012; Chu & Ghahramani, 2005; Bellala
et al., 2010; Karbasi et al., 2012; Zheng et al., 2012;
Proceedings of the 21st International Conference on Artificial Intelligence and Statistics (AISTATS) 2018, Lanzarote, Spain. PMLR: Volume 84. Copyright 2018 by the
author(s).

Percy Liang
Stanford University

Jedynak et al., 2012; Luo et al., 2013; Maji et al., 2014;
Sun et al., 2015). We seek to explain this performance
by providing a condition under which GBS attains a
query cost of O(log n), the information-theoretic optimal query cost.
While there has been much work on establishing that
GBS attains an average cost within a log n factor of the
optimal algorithm (Guillory & Bilmes, 2009; Kosaraju
et al., 1999; Dasgupta, 2004; Chakaravarthy et al.,
2007; Adler & Heeringa, 2008; Chakaravarthy et al.,
2009; Gupta et al., 2010), establishing the asymptotically optimal query cost is a difficult and understudied problem. The few previous works have required
somewhat stringent conditions. One such condition is
“sample-rich” (Naghshvar et al., 2012), which states
that every subset of the hypotheses has a test that returns true on exactly those hypotheses; this requires
an exponential number of tests. Another line of work
(Nowak, 2009, 2011) introduced the more lenient kneighborly condition, which requires that every two
tests be connected by a sequence of tests where neighboring tests disagree on at most k hypotheses. As we
will show in this paper, many problems of a discrete
nature do not satisfy this condition.
In this paper, building on the k-neighborly condition,
we introduce a new, weaker condition called 1/α-splitneighborly, which requires that if neighboring tests disagree on a set of hypotheses V , then there exists a test
that splits off an α fraction of V (note that |V | could
be quite large, whereas k-neighborly requires |V | ≤ k).
We prove that four natural problems satisfy the 1/αsplit-neighborly condition for a constant α: pool-based
linear classifiers, learning monotonic CNF formulas,
discrete object localization, and discrete binary classification. Furthermore, we prove that the
√ value of
k in the k-neighborly analysis is at least n/2 for all
four problems, which yields nearly vacuous bounds. In
summary, by using 1/α-split-neighborly, we show that
Generalized Binary Search achieves an asymptotically
optimal query cost of O(log n) in settings where the
previous k-neighborly analysis tools fail.

Generalized Binary Search For Split-Neighborly Problems

1 point
10 hypotheses

Algorithm 1 Active querying algorithm template
Input: H, X , oracle access to h∗ , method F
V =H
for t = 0, 1, ... do
xt ← F ({(xi , yi )}t−1
i=1 )
Query xt and obtain yt = h∗ (xt )
Update V ← {h ∈ V : h(xt ) = yt }
if |V | = 1 then
return h ∈ V
end if
end for

2 points
4 hypotheses
+

+

+
4 points
1 hypothesis
-

3 points
2 hypotheses
+

-

+

-

Algorithm 2 Generalized Binary Search (F )
t−1
Input: H, X , Previous test results {(xi , yi )}i=1
V = {h ∈ H : h(xi ) = yi , 1 ≤ i ≤ t − 1}
xt ← argminx∈X |Eh∈V [h(x)] − 1/2|
return xt

1.1

Notation

In all cases, we use log to denote log2 . For
a set
P
s∈S f (s)
S and function f , we define Es∈S [f (s)] =
.
|S|
Similarly,
forP a condition C,
we define
1[C(s)]
.
Prs∈S [C(s)] = s∈S|S|

2

Problem statement

+

+

Figure 1: Problem of identifying a linear classifier in a
pool-based active learning setting. Each linear classifier is represented by a red line with an arrow pointing
towards the positive class. Each round, we select a new
test (blue point), after four rounds, we have identified
the true classifier.

Though we focus on the noiseless and well-specified
setting, both conditions can be relaxed: Kääriäinen
(2006) reduces the non-persistent noisy setting (we can
repeatedly query any test) to the noiseless setting, and
Nowak (2011) adapts the GBS algorithm to the misspecified setting (see Section 5 for more details).

Consider a set of n hypotheses H and tests X , where
each h ∈ H is a mapping from X to {0, 1}. We assume that the hypotheses H are identifiable, meaning
that any two hypotheses yield different results on at
least one test. Assume there is a fixed but unknown
hypothesis h∗ ∈ H that we wish to identify. An active querying algorithm performs a sequence of tests;
on each iteration, it uses a method F to select a test
xt based on the results of previous tests and receives
yt = h∗ (xt ) (see Algorithm 1). We evaluate F based
on the worst-case number of queries.

Generalized Binary Search (also known as the “splitting algorithm” and “maximal shrinkage”) is a wellstudied method (Garey & Graham, 1974; Nowak, 2011;
Dasgupta, 2004). GBS maintains the set V ⊆ H of hypotheses consistent with test results thus far, and at
each step, it chooses a test that splits the elements of
V as evenly as possible. See Algorithm 2 for the pseudocode. The optimal worst-case number of queries is
Ω(log n) so if GBS attains O(log n) for a problem, it
is asymptotically optimal.

As an illustrative example, let the set of hypotheses
H be linear classifiers separating 5 data points at the
vertices of a regular pentagon. (see Figure 1). In this
case, |H| = 20 (only including hypotheses with both
+ and − labels). The tests X are data points, and the
test output is an indicator for h∗ classifying that point
as +. Figure 1 shows the queries generated by GBS.
We see that the size of the version space |V | decreases
exponentially, the hallmark of a O(log n) worst-case
query cost. Later, we will prove that GBS indeed attains O(log n) worst-case query cost for this this problem class of linear classifiers on the vertices of convex
polygons.

3
3.1

General analysis
Splits

Intuitively, GBS works well when it can find tests that
split the hypothesis space into roughly equal parts.
The split induced by test x is a partition of the hypotheses into {h ∈ H : h(x) = 0} and {h ∈ H :
h(x) = 1}. Define the split constant of a test x for a
set of hypotheses V as miny∈{0,1} Prh∈V [h(x) = y], the
fraction of hypotheses in the smaller partition. Note
that large split constants are preferred, and 1/2 is the
maximum split constant. As we will see, both the k-

Stephen Mussmann, Percy Liang

both return 0 and 1 by choosing tests randomly.1

Graph of Tests

Δ(𝑥′, 𝑥)

Definition 3.2 (Coherence parameter). The coherence parameter is the largest c such that

𝑥

𝑥′

Δ(𝑥, 𝑥 ′ )

∀h ∈ H : Ex∼P [h(x)] ∈ [c, 1 − c]
for some probability distribution P over tests.
This is a concept that will be used with our condition,
1/α-split-neighborly, as well. From these two definitions, Nowak (2011) showed the following result:

Hypotheses
Figure 2: A test graph on the top and the action
of two neighboring tests x, x0 on the hypotheses on
the bottom. The hypotheses h are represented by
rectangles and the tests by circles that contain the
hypotheses for which the test returns 1. For a kneighborly edge to exist between two tests, the corresponding ∆(x, x0 ) and ∆(x0 , x) must have cardinality
|∆(x, x0 ) ∪ ∆(x0 , x)| ≤ k. If the resulting test graph is
connected, we say the problem is k-neighborly.

neighborly condition (Nowak, 2011) and our new 1/αsplit-neighborly condition imply that for any version
space V , there is a test with a large split constant.
3.2

Earlier work: k-neighborly and coherence
parameter

Tests often have a similarity structure. As an example, for the hypothesis class of linear classifiers, nearby
input points (tests) yield the same result for most hypotheses. We therefore construct a similarity graph
over tests, which will provide a useful analysis tool
that allows us to only reason locally on the graph.
Nowak (2011) defines two tests to be similar if they
disagree on at most k hypotheses. k-neighborly is the
condition that such a similarity graph is connected.
Definition 3.1 (k-neighborly). For any two tests, x
and x0 , define ∆(x, x0 ) = {h ∈ H : h(x) = 0 ∧ h(x0 ) =
1}. Let the test graph contain undirected edges (x, x0 )
for which |∆(x, x0 )∪∆(x0 , x)| ≤ k. A problem instance
is k-neighborly if the test graph is connected.
See Figure 2 for an illustration of the k-neighborly condition. Intuitively, the k-neighborly condition ensures
that between any two tests, we can find a path where
each pair of neighbors in the path are very similar.
Nowak (2011) also defines the coherence parameter,
which ensures an algorithm can easily find tests that

Theorem 3.1 (Nowak, 2011). If a problem has a
coherence parameter c and is k-neighborly, then the
1
log(n) queries, where
worst-case cost of GBS is − log(λ)
1
λ = 1 − min(c, k+2 ).
For large enough c, the k-neighborly analysis yields
worst-case query complexity of O(k log(n)).
Later, we
√
show several examples where k = Ω( n), yielding the
k-neighborly analysis very loose.
3.3

Split-neighborly

The k-neighborly condition is a rather strong condition
since it requires tests that disagree on only k hypotheses. While this sometimes holds for problems with a
continuous structure, such as linear classifiers or continuous object localization, it is often not satisfied for
problems with a discrete nature. Later, in Section 4,
we show a variety √of problems of a discrete nature
where k is at least n/2. Motivated by these discrete
problems, we will now introduce a weaker condition
which we call 1/α-split-neighborly, the main contribution of this paper. In 1/α-split-neighborly, two tests
are not only connected if there is a small number of
hypotheses on which the tests differ, but also if any
subset of the hypotheses that they differ on can be
split evenly (with a split constant of at least α) by
some test.
Definition 3.3 (1/α-split-neighborly). Let α ∈ (0, 12 ]
2
. For any two tests, x and x0 , define ∆(x, x0 ) = {h ∈
H : h(x) = 0 ∧ h(x0 ) = 1}. Define a directed test graph
to have a directed edge (x, x0 ) if for any V ⊆ ∆(x, x0 ),
|V | ≤ 1 or there exists a test x ∈ X such that
Eh∈V [h(x)] ∈ [α, 1 − α]
A problem is 1/α-split-neighborly if the test graph is
strongly connected.
1

Our definition is a simple linear transformation of the
definition in Nowak (2011) to account for notational differences.
2
As a special case, we say a problem is 1-splitneighborly if the graph generated by connecting nodes
where |∆(x, x0 )| ≤ 1 is strongly connected.

Generalized Binary Search For Split-Neighborly Problems

𝑘-neighborly

𝑥′

1/𝛼-split-neighborly

Constant
coherence

GBS achieves O(log n)

Δ(𝑥, 𝑥 ′ ) 𝑥

Figure 4: Relationship between the different conditions, where arrows represent logical implication.

Figure 3: For the problem of identifying linear classifiers in a pool-based active learning setting, an example of two tests that are not connected in the kneighborly graph for small k but are connected in the
1/α-split-neighborly graph for small 1/α. While the size
of ∆(x, x0 ) is large, we can still split any subset of
∆(x, x0 ) because of the other points in the pool.

0 to close to 1, in which case there is a good split, or
there is a large jump in the split constant between
two neighboring tests x and x0 , which implies that
|V ∩ ∆(x, x0 )|/|V | is large. Finally, from the definition
of 1/α-split-neighborly, we can find a test to have a β
split constant of V ∩ ∆(x, x0 ). In summary, the splitneighborly condition and coherence condition allow us
to conclude that for any subset of the hypotheses, there
is a test with a β split constant.

Although it can be more involved to show an edge
between tests in the sense of 1/α-split-neighborly rather
than k-neighborly, it is a more general condition which
makes the similarity graph more connected (see Figure
3 for an example).

From this lemma, we get the following theorem.

The coherence, k-neighborly, and 1/α-split-neighborly
conditions are preserved when we restrict the hypotheses: create a problem with same tests X 0 = X but with
H0 ⊆ H. This is because the conditions all are statements involving a universal quantification over the hypotheses, or subsets thereof.
Furthermore, and most importantly, constant coherence and the split-neighborly condition imply that
GBS has O(log n) query cost. First, we prove the following lemma, showing that constant coherence and
1/α-split-neighborly imply that any subset of H has a
test with a good split constant.
Lemma 3.1. If a problem is 1/α-split-neighborly and
has a coherence parameter of c, then for any V ⊆ H,
|V | ≤ 1 or there exists a test x ∈ X such that
Eh∈V [h(x)] ∈ [β, 1 − β]
where the split constant is


1
β = min c, 1
.
/α + 2
Note that for large c and small α, β ≈ α. See appendix for the full proof; we only give a sketch here.
Intuitively, the coherence parameter ensures that there
is a good split of V or there is both a test that mostly
yields 0 and a test that mostly yields 1 (for hypotheses
V ). If we examine a path of tests x between the two
tests, either Eh∈V [h(x)] varies smoothly from close to

Theorem 3.2. If a problem is 1/α-split-neighborly and
has a coherence parameter of c, then GBS has a worst
log n
, where
case query cost of at most − log(1−β)


1
.
β = min c, 1
/α + 2
From Lemma 3.1, it is clear that after m queries,
we have at most n(1 − β)m hypotheses left. Thus,
the worst-case query cost (to reach one hypothesis) is
log n
− log(1−β) . The precise proof is in the appendix.
Similarly to the k-neighborly condition, for large
enough coherence, the worst-case query cost is
O( α1 log n). Thus, for constant α, we get O(log n)
worst-case query cost, but for α → 0, we do not.
In fact, k-neighborly implies k-split-neighborly (1/αsplit-neighborly, α = 1/k). Thus, our split-neighborly
condition is a generalization of k-neighborly, and comparison between our theorems shows our condition is
strictly more powerful than the k-neighborly condition. See Figure 4 for a diagram.
Proposition 3.1. If a problem is k-neighborly, then
it is k-split-neighborly.
Proof. In the case that k = 1, |∆(x, x0 )| = 1 so
|V | ≤ 1 so the problem is 1-split-neighborly. Note
that any set of hypotheses must have a test that distinguishes at least one of the hypotheses (otherwise
the hypotheses are the same). If two points x and
x0 in the k-neighborly graph have an edge between
them, then |∆(x, x0 ) ∪ ∆(x0 , x)| ≤ k, which implies
|V | ≤ |∆(x, x0 )| ≤ k, and thus either |V | ≤ 1 or there

Stephen Mussmann, Percy Liang

is a test with a 1/k split constant and thus there is
an edge from x to x0 in the k-split-neighborly graph.
Similarly, there is an edge from x0 to x, the k-splitneighborly graph is strongly connected, and the problem is k-split-neighborly.

4

Δ(𝑥, 𝑥 ′ )

All of the proofs have a similar structure for proving
1/α-split-neighborly. First, fix a subset of hypotheses
V ⊆ ∆(x, x0 ). Then, by assuming there is no test with
a good split constant α, we can leverage the structure of the problems to conclude that the size of V is
small. Since any two hypotheses disagree on at least
one test (identifiability of hypotheses), we can always
split off one of the hypotheses for a split constant of
1/|V | which is a good split if |V | ≤ 1/α.
Since there is no test with a split constant α, any test
either yields 1 on the vast majority of hypotheses in
V or yields 0 on the vast majority of hypotheses in V .
Thus, we partition the tests into two sets,
X + = {x ∈ X : Pr [h(x) = 1] > 1 − α}
h∈V

X − = {x ∈ X : Pr [h(x) = 1] < α} = X − X +
h∈V

Several of the arguments will leverage the structure of
this partition and use union bound to show that the
probability of a single hypothesis is high, and thus V
is small.
Two-dimensional linear classifiers with
convex polygon data pool

Suppose we have a pool of unlabeled data points and
our set of hypotheses is linear classifiers in the transductive setting (we group all hypotheses with the same
output on all unlabeled data points together). We examine the case of two dimensions.
Problem 1 (Linear classifiers on convex polygon data
pool). Let X be a set of m points x ∈ R2 such that the
points are the vertices of a convex polygon. Let H be
equivalence classes of linear classifiers that have the

𝑥′

𝑥

Application of analysis

In this work, we establish the 1/α-split-neighborly condition for four problems: two-dimensional linear classifiers on the vertices of a convex polygon, learning
monotonic disjunctions and CNF formulas, discrete
object localization (under two different conditions),
and discrete linear classifiers. We show that GBS
achieves O(log n) cost on these problems under conditions on H by showing that the problems are 1/α-splitneighborly and have constant coherence. Further, we
show the inadequacy of the k-neighborly analysis for
each of these problems.

4.1

⌈𝑚/4⌉

⌈𝑚/4⌉
Figure 5: An illustration of ∆(x, x0 ) for linear classifiers on a data pool forming the vertices of a convex
polygon. Note that we can split any subset of ∆(x, x0 )
with a split constant of at least 1/3 because the tests
are interleaved in a sequence with the hypotheses.
same output on X and such that
P


1 3
x∈X h(x)
∈
,
.
|X |
4 4
This last constraint restricts the classifiers to those
with balanced labels. This ensures a good coherence
parameter; otherwise,
no algorithm can perform better
√
than Θ(m) = Θ( n).
We will now show that the k-neighborly analysis for
this problem is poor. See Figure 5 for a diagram. For
adjacent points x and x0 , |∆(x, x0 )| = m − 2dm/4e + 1.
Further note that n
= |H| = m(m − 2dm/4e + 1) 3 .
√
n
0
Thus, |∆(x, x )| ≥ 2 (for m ≥ 4) and so the k for the
√
k-neighborly analysis is at least 2n .
However, it is clear from Figure 5 that ∆(x, x0 ) is a
sequence of hypotheses with tests interleaved. Thus,
we can split ∆(x, x0 ) with at least a split constant of
1/3 and to get the following proposition,
Proposition 4.1. The problem of learning a linear
classifier on a convex polygon data pool is 3-splitneighborly.
Note that because of the constraint that the minority
label is at least 1/4, the coherence parameter is at least
c = 1/4. Thus, the worst case query complexity is at
log n
≤ 3.2 log n.
most − log(1−1/5)
4.2

Monotonic CNF formulas

In this section, we examine the problem of learning
monotonic CNF formulas from function evaluations.
To begin, we study the case of a single disjunction,
such as the following,
x4 ∨ x7 ∨ x9
3

We have 2 linear classifiers for each line, but we are
double counting.

Generalized Binary Search For Split-Neighborly Problems

A. 0 0 0 0 0 0 1 1 1 1 1 1
1 0 0 0 0 0 1 1 1 1 1 1
B. 𝑥 ∨ ⋯
1

C.

𝑥−
𝑥+

ℎ ∈ 𝑉 ⊆ Δ(𝑥 − , 𝑥 + )
has this form

𝑍

0 0 0 0 1 1 1 1 1 1 1 1

𝑥′

D. 0 1 0 0 1 1 1 1 1 1 1 1 𝑥 (2)
0 0 1 0 1 1 1 1 1 1 1 1 𝑥 (3)
0 0 0 1 1 1 1 1 1 1 1 1 𝑥 (4)
E.
𝑥1 ∨ 𝑥2 ∨ 𝑥3 ∨ 𝑥4

Permuted

from

1/(m + 1) and the proof is complete.
Now, if there are no tests with a good split, each test
must either yield 1 or 0 for the vast majority of hypotheses in V . Thus, we can define the following two
sets.
X + = {x ∈ X : Pr [h(x) = 1] > 1 − q}

from

Strictly greater than
1− 𝑍 +1 𝑞
proportion

Figure 6: A proof illustration for the disjunction problem being split-neighborly.
Problem 2 (Disjunction). Let the elements of H be
a disjunction over d variables without any negations
where the disjunction has at most m variables. Let X
be the set of length d bit assignments.
First, note that h(0d ) = 0 and h(1d ) = 1 for all h ∈ H
and thus the coherence parameter is c = 1/2. The kneighborly
is lacking for this problem. Note,

Pm analysis
|H| = i=1 di . However, the bit string 0d ∈ X dis
Pm
agrees with all other x ∈ X for i=1 d−1
i−1 hypotheses.
√
So for m ≥ 2, d ≥ 2m, then k ≥ n. See the appendix
for details. On the other hand, our split neighborly
analysis achieves the optimal rate in the case where m
is constant and d goes to infinity.
Theorem 4.1. The single disjunction problem is
(m + 1)-split-neighborly.
Proof. A graphic for the proof is shown in Figure 6.
We will show that there are edges between tests that
differ by just one bit. This will suffice since such a
graph is strongly connected. In particular, we show
that the test graph has a bidirectional edge from x to
x0 if ||x − x0 ||1 = 1.
Let x+ be the value of x or x0 with more 1’s (and let
x− be the other one). Note that from monotonicity,
|∆(x+ , x− )| = 0 so there is a directed edge from x+ to
x− .
For the other direction, fix a subset V ⊆ ∆(x− , x+ ).
Without loss of generality, let x+ and x− differ in
−
the first coordinate so x+
1 = 1 and x1 = 0 and
+
−
∀i > 1 : xi = xi . See row A of Figure 6. Because
V ⊆ ∆(x− , x+ ), all hypotheses in V include x1 in the
disjunction. See row B of Figure 6.
For ease of notation, let q = 1/(m+1). We will proceed
by showing that if there is no test with a good split,
Eh∈V [h(x)] ∈ [q, 1 − q], then |V | ≤ m + 1. Then, either
|V | ≤ 1 or there is a test with split constant at least

h∈V

X − = {x ∈ X : Pr [h(x) = 1] < q} = X − X +
h∈V

0

Let x be the the element of X − with the fewest 0’s.
Since x0 ∈ X − , x01 = 0. Let Z be the other indices of
the 0’s. If |Z| = 0, then |∆(x− , x+ )| = |{x1 }| = 1 so
|V | ≤ 1 and we are done. Define {x(j) }j∈Z to be the
test resulting from x0 and changing the j th bit to a 1.
By the minimal definition of x0 , ∀j ∈ Z : x(j) ∈ X + .
See rows C and D of Figure 6.
We now derive a useful equation. Note that for any
subset Z 0 ⊆ Z, from the definition of X + and X − and
union bound, Prh∈V [h(x0 ) = 0 ∧ ∀j ∈ Z 0 : h(x(j) ) =
1] > 1 − (|Z 0 | + 1)q. From the property of disjunctions,
this implies Prh∈V [h has variables at Z 0 ∪ {1}] > 1 −
(|Z 0 | + 1)q. See row E of Figure 6.
If |Z| ≥ m, then this means that we can choose a subset Z 0 of size m. Prh∈V [h includes m + 1 variables] >
1 − (m + 1)q = 0. This means there is a non-zero
probability of a hypothesis with m + 1 variables which
is impossible, since our disjunctions don’t have more
than m variables. So |Z| ≤ m − 1.
We are nearly done. Note that the left side of the
useful equation is exactly 1/|V |. Therefore, 1/|V | >
1 − (|Z| + 1)q ≥ 1 − mq ≥ 1/(m + 1). Rearranging, we
find that |V | < m + 1 and we are done.
We now examine the more general monotonic CNF
problem from function evaluations. An example of
such a monotonic formula is:
(x1 ∨ x4 ∨ x5 ) ∧ (x2 ∨ x7 ∨ x8 ).
Problem 3 (Conjunction of disjunctions). Let H be a
conjunction of ` m-disjunctions over d variables without any negations, and where each variable does not
appear in multiple disjunctions. Let X be the set of
length d bit assignments.
Note that there is an isomorphism between conjunctions of disjunctions and disjunctions of conjunctions
by flipping the test bits and the result bit.
Additionally,√for a general setting shown in the appendix, k ≥ n which renders the k-neighborly analysis very poor.
However, the split-neighborly analysis suffices,

Stephen Mussmann, Percy Liang

Δ(𝑥, 𝑥 ′ )

Theorem 4.2. The conjunction of disjunctions problem is (m + 1 + 3(l − 1))-split-neighborly.
The proof is in the appendix. Note that the value of
1/α does not depend on the number of variables, so
GBS is efficient even for very large d when m, l are
constant.
4.3

Other
Tests

𝑥

𝑥′

Object localization in Zd

Consider the problem of object localization (Chen
et al., 2015) where we try to locate an object based
on spatial queries. In this work, we wish to find the
location z of an object in space or in an image by asking queries of the form “Is z close to point x?”. We
can discretize the space into the grid of integers and
define “closeness” by as whether z − x is in some set
S (e.g., an `p ball).
In this way, hypotheses and tests are both indexed by
vectors of integers. For concreteness, for an `p norm
ball, a test x returns the result of kx − zkp ≤ `.
Problem 4 (Object localization). Fix a set S ⊆ Zd
representing the sensing field
H ⊆ {hz }z∈Zd

X = Zd

hz (x) = 1[x − z ∈ S]

Note that there are infinitely many integer vectors, but
we can take a bounded region as the hypothesis space.
Note that if the bounded region of the hypothesis space
is too large, the coherence parameter would be very
small, and greedy would not perform well (and any
algorithm for that matter, since the algorithm would
have to do a linear search). One way to make the
coherence parameter c = 1/2 is to choose a x∗ and
ensure that H ⊆ {hz : z − x∗ ∈ S}.
For cases where S is an axis-symmetric box, or equivalently where we use a weighted `∞ norm, the problem
is split-neighborly.

Figure 7: For the object localization problem where
S is an axis-symmetric box, the 1/α-split-neighborly
graph has edges between adjacent points, for example
x and x0 in this figure. Thus, ∆(x, x0 ) will be a flat
box. This figure shows that for d = 2, the problem
is 3-split-neighborly. In fact, the problem is 4-splitneighborly for all d.
The proof is in the appendix and uses union bound
with the partition of X into X − and X + . For this
problem, k must be at least the
√ largest, axis-aligned
“shadow” which for d ≥ 2, k ≥ n.
4.4

Discrete binary linear classifier

Linear classifiers are a classic type of function where
the output label is y = 1[w·x+b > 0]. We consider the
active learning setting where H is a set of (w, b) pairs
and X are points x in the feature space. In fact, this
is the problem covered previously by Nowak (2011)
where w and x take continuous values.
Here, we consider the setting of discrete linear classifiers, where x ∈ {0, 1}d and w ∈ {−1, 0, 1}d .
Problem 5 (Discrete Binary Linear Classifier).

Theorem 4.3. The object localization problem where
S is an axis-symmetric box is 4-split-neighborly.

H ⊆ {hb,w }b∈Z,w∈{−1,0,1}d

The proof is in the appendix. See Figure 7 for some
intuition. Note that the value of k for this problem
is the largest cross-sectional
volume of the box, which
√
for d ≥ 2, k ≥ n.

hb,w (x) = 1[w · x > b]

For axis-symmetric, axis-convex (weaker than convex)
sets S, we have a dimension-dependent bound. By an
axis-convex set S, we mean that if two points in S
differ in only one dimension, then all integral points
between them are also in S.
Theorem 4.4. If S is a bounded, axis-symmetric,
axis-convex set, the object localization problem is
(4d + 1)-split-neighborly.

X = {0, 1}d
with the following holding for all hypotheses (w(+) and
w(−) are the number of positive and negative vector
components for w, respectively):
w(+) − b ≤ r(w(−) + b) −

d
8

w(−) + b ≤ r(w(+) − b − 1) −

d
8

Intuitively, w(+) −b is the maximum “overshoot” of the
threshold and w(−) + b is the maximum “undershoot”.

Generalized Binary Search For Split-Neighborly Problems

We require that the ratio between these quantities is
at most r with the addition of an additive constant.
Theorem 4.5. The discrete binary linear classifier
problem is max(16, 8r)-split-neighborly.
The coherence parameter will be constant c if there
is some data distribution such that each hypothesis
yields a balanced label distribution (at least probability c of minority label). Intuitively, this is necessary
since if the labels are very unbalanced, it may take
many queries to even find a minority label. With this
condition, GBS achieves O(log n) on the discrete binary linear classifiers problem.
On the other hand, the k-neighborly analysis does not
work here, as before. In the special case where d is
divisible by 4, b = d/4 − 1 and there are an equal
number of 1 and 0 weights (just√for making the calculation simpler), for d ≥ 4, k ≥ n. See the Appendix
for more details.

5

Discussion and related work

The GBS algorithm, or more generally, choosing the
test that maximizes the information gain, has several
approximations and variants. The greedy information
gain technique was introduced in MacKay (1992) and
used or extended in active learning (Jedynak et al.,
2012), ranking learning (Chu & Ghahramani, 2005),
comparison based search (Karbasi et al., 2012), image
segmentation (Maji et al., 2014), structured prediction
(Sun et al., 2015; Luo et al., 2013), group identification (Bellala et al., 2010), and graphical models (Zheng
et al., 2012). As the active learning survey of Settles
(2012) notes, “all of the general query frameworks we
have looked at contain a popular utility function that
can be viewed as an approximation to [information
gain] under certain conditions.” Thus, greedy information gain is seen as the gold standard, and there
has been significant work finding approximations and
extensions. Our work examines the other side of GBS
and tries to understand that gap between GBS and
the optimal solution.
A large body of literature exists on the analysis of GBS
and close relatives in the noiseless and well-specified
version of the sequential hypothesis testing problem,
known as the optimal decision tree problem (Guillory
& Bilmes, 2009; Kosaraju et al., 1999; Dasgupta, 2004;
Chakaravarthy et al., 2007; Adler & Heeringa, 2008;
Chakaravarthy et al., 2009; Gupta et al., 2010). These
analyses, which borrow ideas from submodular analysis, yield an average cost ratio of O(log n), where the
average cost ratio for a method is defined as the ratio between the expected cost of the method and the
expected optimal cost (note that this is significantly

worse than an average query cost of O(log n)). Furthermore, there exists a problem where GBS achieves
a average cost ratio of Θ(log n/ log log n) (optimal is
Θ(log n) but GBS is Θ(log2 n/ log log n)), so the general upper bound for GBS is very close to tight (Dasgupta, 2004). In our work, we show that GBS achieves
a constant factor cost ratio, that is, within a constant
factor of the optimal cost. In many natural settings
such as linear classification, the hypothesis space is exponentially large in the dimension (i.e. n = 2O(d) ), so
existing guarantees are O(d) times the optimal, which
itself is O(d) for many problems. In our work, we prove
in multiple settings that GBS achieves the asymptotically optimal query cost.
Other works extend the noiseless and well-specified assumptions to more general frameworks. Nowak (2011)
provides a way to adapt GBS to the mis-specified
case with only a constant factor increase in the query
complexity that ensures GBS never performs worse
than randomly querying tests (the naive approach).
Kääriäinen (2006) provides a reduction from the noisy
case to the noiseless case. There are two different noise
settings which are handled separately in the literature,
persistent noise (tests are not repeatable) and nonpersistent noise (tests are repeatable). Earlier work
(Nowak, 2009, 2011; Naghshvar et al., 2012) that has
handled noise has addressed i.i.d. noise with repeatable tests, where the outputs of the deterministic problem are flipped with a constant probability p. In the
case of non-persistent i.i.d. noise, Kääriäinen (2006)
presents a technique to reduce the noisy case to the deterministic case by repeatedly querying tests and using
the majority vote, so that with high probability we attain the uncorrupted test result. Thus, while our work
might appear to only handle the noiseless case, it actually handles the non-persistent noise case as well.
Theoretical explanations for the effectiveness of GBS
are still incomplete. Although GBS always achieves
a cost ratio of O(log n) (Guillory & Bilmes, 2009), in
the large hypothesis space regime, this factor could
be very large. Furthermore, there do exist problems
for which GBS performs much worse than the optimal (Dasgupta, 2004). These examples, however, tend
to be contrived. Anecdotally, from the sample problems in this paper, we found that GBS is effective for
most “natural” problems. In conclusion, we have made
progress on characterizing this observation by introducing the 1/α-split-neighborly condition, which provably ensures that GBS achieves the asymptotically optimal query cost.
Acknowledgments
This research was supported by NSF grant DGE1656518.

Stephen Mussmann, Percy Liang

References
Adler, Micah and Heeringa, Brent. Approximating optimal binary decision trees. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pp. 1–9. Springer, 2008.
Bellala, Gowtham, Bhavnani, Suresh, and Scott, Clayton. Extensions of generalized binary search to
group identification and exponential costs. In Advances in Neural Information Processing Systems,
pp. 154–162, 2010.
Chakaravarthy, Venkatesan T, Pandit, Vinayaka,
Roy, Sambuddha, Awasthi, Pranjal, and Mohania, Mukesh. Decision trees for entity identification: approximation algorithms and hardness results. In Proceedings of the twenty-sixth ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp. 53–62. ACM, 2007.
Chakaravarthy, Venkatesan T, Pandit, Vinayaka, Roy,
Sambuddha, and Sabharwal, Yogish. Approximating decision trees with multiway branches. In International Colloquium on Automata, Languages, and
Programming, pp. 210–221. Springer, 2009.
Chen, Yuxin, Javdani, Shervin, Karbasi, Amin, Bagnell, J Andrew, Srinivasa, Siddhartha S, and
Krause, Andreas. Submodular surrogates for value
of information. In AAAI, pp. 3511–3518, 2015.
Chu, Wei and Ghahramani, Zoubin. Extensions of
gaussian processes for ranking: semisupervised and
active learning. Learning to Rank, pp. 29, 2005.
Dasgupta, Sanjoy. Analysis of a greedy active learning
strategy. In Advances in neural information processing systems, pp. 337–344, 2004.
Garey, Michael R and Graham, Ronald L. Performance bounds on the splitting algorithm for binary
testing. Acta Informatica, 3(4):347–355, 1974.
Guillory, Andrew and Bilmes, Jeff. Average-case active learning with costs. In International Conference on Algorithmic Learning Theory, pp. 141–155.
Springer, 2009.
Gupta, Anupam, Nagarajan, Viswanath, and Ravi, R.
Approximation algorithms for optimal decision trees
and adaptive tsp problems. In International Colloquium on Automata, Languages, and Programming,
pp. 690–701. Springer, 2010.
Jedynak, Bruno, Frazier, Peter I, and Sznitman,
Raphael. Twenty questions with noise: Bayes optimal policies for entropy loss. Journal of Applied
Probability, 49(01):114–136, 2012.
Kääriäinen, Matti.
Active learning in the nonrealizable case. In International Conference on Algorithmic Learning Theory, pp. 63–77. Springer, 2006.

Karbasi, Amin, Ioannidis, Stratis, et al. Comparisonbased learning with rank nets. arXiv preprint
arXiv:1206.4674, 2012.
Kosaraju, S Rao,
Borgstrom, Ryan.
lem. In Workshop
tures, pp. 157–168.

Przytycka, Teresa M, and
On an optimal split tree probon Algorithms and Data StrucSpringer, 1999.

Luo, Wenjie, Schwing, Alex, and Urtasun, Raquel. Latent structured active learning. In Advances in Neural Information Processing Systems, pp. 728–736,
2013.
MacKay, David JC. Information-based objective functions for active data selection. Neural computation,
4(4):590–604, 1992.
Maji, Subhransu, Hazan, Tamir, and Jaakkola,
Tommi S. Active boundary annotation using random map perturbations. In AISTATS, pp. 604–613,
2014.
Naghshvar, Mohammad, Javidi, Tara, and Chaudhuri, Kamalika. Noisy bayesian active learning.
In Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on, pp.
1626–1633. IEEE, 2012.
Nowak, Robert. Generalized binary search. In Communication, Control, and Computing, 2008 46th
Annual Allerton Conference on, pp. 568–574. IEEE,
2008.
Nowak, Robert. Noisy generalized binary search. In
Advances in neural information processing systems,
pp. 1366–1374, 2009.
Nowak, Robert D. The geometry of generalized binary
search. IEEE Transactions on Information Theory,
57(12):7893–7906, 2011.
Settles, Burr. Active learning. Synthesis Lectures on
Artificial Intelligence and Machine Learning, 6(1):
1–114, 2012.
Sun, Qing, Laddha, Ankit, and Batra, Dhruv. Active
learning for structured probabilistic models with histogram approximation. In Proceedings of the IEEE
Conference on Computer Vision and Pattern Recognition, pp. 3612–3621, 2015.
Young, Linda J and Young, Jerry H. Sequential hypothesis testing. In Statistical Ecology, pp. 153–190.
Springer, 1998.
Zheng, Alice X, Rish, Irina, and Beygelzimer, Alina.
Efficient test selection in active diagnosis via entropy
approximation. arXiv preprint arXiv:1207.1418,
2012.

Generalized Binary Search For Split-Neighborly Problems

6

Appendix
X

6.1

Split-neighborly proofs

P (x)S(x) ∈ [β, 1 − β]

x∈X

Theorem 3.2. If a problem is 1/α-split-neighborly and
has a coherence parameter of c, for

There are two possibilities, either there exists a test x
such that

1
β = min(c, 1
)
/α + 2

S(x) = Eh∈V [h(x)] ∈ [β, 1 − β]
log n
− log(1−β)
log n
most H(β)

GBS has a worst case query cost of at most

and GBS has an average query cost of at
where H(p) is the entropy of a Bernoulli(p) random
variable
Proof. This theorem will follow from the next three
lemmas.
Lemma 3.1. If a problem is 1/α-split-neighborly and
has a coherence parameter of c, then for any V ⊆ H,
|V | ≤ 1 or there exists a test x ∈ X such that

in which case, this is the exact conclusion statement
and we are done, or that there exists no test with a
split constant in [β, 1 − β]. If there exists no test with
a split constant in [β, 1 − β] but the weighted combination is in [β, 1 − β], then there exists tests x and x0
such that S(x) < β and S(x0 ) > 1 − β
Since the problem is 1/α-split neighborly, there exists a
graph over the tests that is strongly connected. Thus,
there is a path from x to x0 . Since S(x) < β and
S(x0 ) > 1 − β and since ∀x00 ∈ X : S(x00 ) 6∈ [β, 1 − β],
there must be an edge (x0 , x1 ) along the path where
S(x0 ) < β and S(x1 ) > 1 − β. Thus,

Eh∈V [h(x)] ∈ [β, 1 − β]

Pr [h(x0 ) = 1] = Eh∈V [h(x0 )] < β

h∈V

Pr [h(x1 ) = 1] = Eh∈V [h(x1 )] > 1 − β

where β is defined as above.
Proof. Fix a subset V ⊆ H. Assume |V | > 1, otherwise we are done.

h∈V

Combining these two yields,

From the assumption, we have a coherence parameter
of

Pr [h(x0 ) = 0 ∧ h(x1 ) = 1] > 1 − 2β

h∈V

Recall ∆(x0 , x1 ) = {h ∈ H : h(x0 ) = 0, h(x1 ) = 1}
c≥β
Pr [h ∈ ∆(x0 , x1 )] > 1 − 2β

From the definition, this means that there exists a
probability distribution on the tests P such that for
any hypothesis h,
X

P (x)h(x) ∈ [β, 1 − β]

h∈V

|V ∩ ∆(x0 , x1 )|
> 1 − 2β
|V |
Recall from the definition of β that

1
1/α+2

≥ β. Thus

x∈X
1/α
1
β
=1
≥
1 − 2β ≥ 1 − 2 1
/α + 2
/α + 2
α

Since this is true for all h ∈ H, this is also true for all
convex combinations. Thus,
Thus,
Eh∈V [

X

P (x)h(x)] ∈ [β, 1 − β]

x∈X

X

|V ∩ ∆(x0 , x1 )|
β
>
|V |
α

P (x)Eh∈V [h(x)] ∈ [β, 1 − β]

x∈X

For simplicity, define the split constant S(x) =
Eh∈V [h(x)]. Thus,

For brevity, define ∆ = ∆(x0 , x1 ). Since there is an
edge (x0 , x1 ) in the 1/α-neighborly graph, for any subset including V ∩ ∆ ⊆ ∆, either |V ∩ ∆| ≤ 1 or there
exists a test x̂ such that,

Stephen Mussmann, Percy Liang

Eh∈V ∩∆ [h(x̂)] ∈ [α, 1 − α]
|V ∩∆(x0 ,x1 )|
β
>α
.
|V |
|V ∩∆(x0 ,x1 )|
β
> α and |V | >
|V |

Lemma 6.1. If, for any V ⊆ H, |V | ≤ 1 or there
exists a test x ∈ X such that

First, |V ∩ ∆| =
6 0, since |V | > 1 and
If |V ∩ ∆| = 1, then,

β
1 so 12 ≥ |V1 | > α
≥ β. Since the hypotheses are
identifiable, any pair of hypotheses yield a different
result on some test, so we can always find a test with
a split constant of at least |V1 | , and this implies the
result of the theorem.

In the other case, where |V ∩ ∆| > 1, we have all the
necessary pieces and it’s just a matter of crunching the
algebra.
P

h(x̂)
|V |

h∈V

Eh∈V [h(x̂)] =

Eh∈V [h(x)] ∈ [β, 1 − β]
then GBS has a worst case query cost of at most
log n
1
log( 1−β
)

Proof. After m queries, there are at most max(1, (1 −
β)m n) remaining hypotheses since greedy will choose
a test with a split constant of at least β (a split with
respect to the hypotheses without a prior) and will terminate when there is a single hypothesis. Thus, when
(1 − β)m n ≤ 1, the algorithm must have terminated.
log n
the alRearranging, we see that when m ≥ log(
1
)
1−β

gorithm must have terminated. This means that the
log n
worst case query cost must be at most log(
.
1
)
1−β

P

h(x̂)
≥ h∈V ∩∆
|V |
P
β h∈V ∩∆ h(x̂)
≥
α
|V ∩ ∆|

Lemma 6.2. If, for any V ⊆ H, |V | ≤ 1 or there
exists a test x ∈ X such that

β
Eh∈V ∩∆ [h(x̂)]
α

log n
then GBS has an average query cost of at most H(β)
where H(p) is the entropy of a Bernoulli(p) random
variable

≥

≥

Eh∈V [h(x)] ∈ [β, 1 − β]

β
α=β
α

Proof. Define H(p) as the entropy of a Bernoulli random variable with probability p.

Additionally,
P

P
=

≤
≤

h∈V ∩∆

h(x̂) +

h(x̂)
|V |

h∈V

Eh∈V [h(x̂)] =

P

h∈V \∆

h(x̂)

|V |
(1 − α)|V ∩ ∆| +

P

h∈V \∆

f (V ) = E[average queries remaining while at subset V ]
(1)
We will prove by induction on increasing subsets that

h(x̂)

f (V ) ≤

|V |
(1 − α)|V ∩ ∆| + |V | − |V ∩ ∆|
|V |
≤1−α
≤1−α

|V ∩ ∆|
|V |

β
=1−β
α

Thus, we have that
Eh∈V [h(x̂)] ∈ [β, 1 − β]

log(|V |)
H(β)

(2)

Note that the base case is that f ({h}) = 0 because
we are done when there is just one hypothesis left.
Note that this suffices to show that the total runtime
is log(n)/H(β) because |V | = n at the beginning of
the algorithm.
Let A, B be a partition of V based on a test split.
Without loss of generality, let |A| ≤ |B|, so |A| ≤
1/2|V |. Based on the recursive definition of cost and
there is a test with a split constant of at least β (so
GBS will choose a test with a split constant of at least
β),

which is the conclusion of the lemma.
f (V ) ≤

max

A,B,|A|/|V |∈[β,1/2]

|B|
|A|
f (A) +
f (B) + 1
|V |
|V |

Generalized Binary Search For Split-Neighborly Problems

From the induction hypothesis,
≤ max
...

|A| log |A| |B| log |B|
+
+1
|V | H(β)
|V | H(β)

≤

log |A| +

|B|
|V |

i

i=1


m 
X
d−1

k≥
|A|
max... |V
|

m  
X
d

n=

i=1

log |B| + H(β)

H(β)
k ≥1+

i−1

m−1
X

d−1
i

i=1

≤

|A|
max... |V
|

log

|A|
|V |

+

|B|
|V |

log

|B|
|V |

+ H(β) + log |V |

H(β)
k2 − n ≥ 1 + 2
≤

−

Note that 2

Value of k
Disjunctions

For the disjunctions problem, for m ≥ 2, d ≥ 2m,

d−1
i



≥

d
i



k2 − n ≥ 1 + (

since i ≤ m − 1 ≤ d/2.

m−1
X
i=1


 
d−1 2
d
) −
i
m

2  
d−1
d
−
m−1
m



d−1
d−1
≥
(
− d/m)
m−1
m−1


Thus, we have proved the statement by induction and
this suffices to show that the total runtime is at most
log(n)/H(β).

Proof. In the case that k = 1, |∆(x, x0 )| = 1 so |V | ≤ 1
so the problem is 1-split-neighborly. Assume k > 1.
Note that any set of hypotheses must have a test that
distinguishes at least one of the hypotheses (otherwise
the hypotheses are the same). If two points x and
x0 in the k-neighborly graph have an edge between
them, then |∆(x, x0 ) ∪ ∆(x0 , x)| ≤ k, which implies
|∆(x, x0 )| ≤ k, and thus either |∆(x, x0 )| ≤ 1 or there
is a test with a 1/k split constant and thus there is
an edge from x to x0 in the k-split-neighborly graph.
By a similar argument, there is also an edge from x0
to x. Since the k-neighborly graph is connected and
each edge corresponds to a bidirectional edge in the
k-split-neighborly graph, the k-split-neighborly graph
is strongly connected and thus the problem is k-splitneighborly.

  
d
d
−
i
m

i=1

log(|V |)
f (V ) ≤
H(β)

6.2.1

m−1
X

[β, 1/2]

Proposition 3.1. If a problem is k-neighborly and has
a uniform prior, then the problem is k-split-neighborly.


m−1
X d − 1
d−1
+(
)2
i
i
i=1

i=1

H(β)

Note that since
∈
(the condition of the
|A|
max), H( |V
)
≥
H(β).
Thus,
the
max is non-positive,
|
and thus,

6.2

m−1
X

|A|
max... −H( |V
| ) + H(β) + log |V |

|A|/|V |



≥

Since m ≥ 2,

≥


d−1
− d/2
1

≥ d/2 − 1
≥m−1
≥0
Thus, k 2 − n ≥ 0 and so k ≥
6.2.2

√

n.

Monotonic CNF


d
Note that n = |H| = l!1 m,m,...,m,d−lm
. All of the
bit strings with strictly less than l ones will be trivially connected in the k-neighborly graph, because
they yield 0 on all hypotheses. However, the closest test to connect them to the rest of the graph
is the bit string 1l 0d−l ∈ X , which disagrees on
d−l
m−1,m−1,...,m−1,d−lm ≤ k hypotheses. We examine
the case where d ≥ 2ml and m ≥ 2.
For the monotonic CNF formulas, recall that


1
d
n = |H| =
l! m, m, ..., m, d − lm

Stephen Mussmann, Percy Liang


k≥


d−l
m − 1, m − 1, ..., m − 1, d − lm

For d ≥ 2ml and m ≥ 2, k ≥


√

n
≤
k2

n.


d−l
≤k
m − 1, m − 1, ..., m − 1, d − lm

=

4c
2c

3c 2
c



(4c)!c!c!
(3c)!(3c)!

Note that we have the common Stirling’s approximation,

and


1
d
n=
l! m, m, ..., m, d − lm
=
=

√

d!
1
l! (m!)l (d − lm)!

2πnn+1/2 e−n ≤ n! ≤ enn+1/2 e−n

Thus,

(d − l)!
1 d!(d − 2l)! (d − l)!
(m − 1)!l (d − lm)! ml (d − l)!2 l!(d − 2l)!


1 d!(d − 2l)! d − l
≤k l
m (d − l)!2
l

e3 (4c)4c+1/2 cc+1/2 cc+1/2 e−6c
n
≤
k2
2π(3c)3c+1/2 (3c)3c+1/2 e−6c
√
2e3 c(4c)4c cc cc
=
6π(3c)3c (3c)3c
√
e3 c44c
=
3π33c 33c

Since d ≥ 2ml ≥ 4l,

n≤k



2l d − l
ml
l

=

Since d − l ≥ 2l(m − 1) and m ≥ 2

e3 √ 256 c
c(
)
3π
729
≤1




d−l
n≤k
l(m − 1)

n≤k

for c ≥ 1.


d−l
m − 1, m − 1, ..., m − 1, d − lm

Thus, for d ≥ 4,
n
≤1
k2
√
k≥ n

n ≤ k2
√
k≥ n
6.2.3

Discrete Linear Classifier

6.3

Necessity of Dependencies

Recall that we are in the special case where d is divisible by 4, b = d/4 − 1 and there are an equal number
of 1 and 0 weights (d/2).

6.3.1

All tests with fewer than d/4 1’s will yield a result of
0 for all hypotheses. The test with the next fewest
hypotheses that yield 1 will be a test with exactly d/4
1’s. Thus, k is at least the number of such hypotheses
that yield 1.

For arbitrary data points where the points are not
the vertices of a convex polygon, the linear classifier
problem is not 1/α-split-neighborly for constant α. A
counter-example is shown in Figure 8.
6.3.2



Disjunctions



n=

d
d/2

k≥



3d/4
d/4

For simplicity, define c = d/4.

Linear classifiers on convex polygon
data pool

The linear dependence on m for the disjunctions is
necessary because of the case where d = m + 1, and
|H| = d (each h ∈ H lacking one variable). In this
1
case, there are no tests with split constants of m
, so the
problem cannot be better than (m−2)-split-neighborly
(recall coherence c = 1/2).

Generalized Binary Search For Split-Neighborly Problems

x− be the other one). Note that |∆(x+ , x− )| = 0 so
there is a directed edge (x+ , x− ).
For the other direction, fix a subset V ⊆ ∆(x− , x+ ).
Without loss of generality, let x+ and x− differ in the
−
first coordinate so x+
1 = 1 and x1 = 0 and ∀i > 1 :
+
−
xi = xi .

Figure 8: A counterexample that shows a non-convex
data pool need not be split-neighborly. Note that we
can at most split off 1 of the n hypotheses by querying
one of the points from the lower half. However, the
problem has coherence close to 1/2 and thus it cannot
be 1/α-split-neighborly for constant α.

For a proof by contradiction, the problem is not (m +
1)-split-neighborly so that |V | > 1 and there is no
test x such that Eh∈V [h(x)] ∈ [q, 1 − q], where q =
1/(m + 1).
Let
X + = {x ∈ X : Pr [h(x) = 1] > 1 − q},
h∈V

X − = {x ∈ X : Pr [h(x) = 1] < q} = X − X + .
h∈V

6.3.3

Monotonic CNF

For the monotonic CNF problem, the linear dependence on m is necessary because of the case where
l = 1, d = m + 1, and |H| = d (each h ∈ H lacking
one variable). In this case, there are no tests with split
1
, so the problem cannot be better than
constants of m
(m − 2)-split-neighborly (recall coherence c = 1/2).
Furthermore, the linear dependence on l is necessary
because of the problem where m = 1, d = l + 1, and
|H| = d (each h ∈ H lacking one variable). For this
problem, there are no tests with split constants of 1l ,
so the problem cannot be better than (l − 2)-splitneighborly. Thus, although the linear dependence on
m and l is necessary, it may be possible to improve the
constants.
6.3.4

Object Localization

For object localization with the axis-symmetric, axisconvex set S, the dependence on d is necessary because
if we use the set S = {jei : |j| ≤ l, 1 ≤ i ≤ d} and
consider the set of hypotheses, {±lei : 1 ≤ i ≤ d}, the
1
but
problem has no test with split constant of 2d−1
has coherence c = 1/2, so it can’t be (2d − 3)-splitneighborly.
6.4

Monotonic CNF

Theorem 4.2. The Conjunction of Disjunctions problem is (m + 1 + 3(l − 1))-split-neighborly.
Proof. We prove this theorem by induction on l. First,
for the base case l = 1.

Let x0 be the the element of X − with the fewest 0’s and
let the 0’s be at indices Z (note 1 ∈ Z). If |Z| < m,
then h(x0 ) = 1 for all h since the disjunctions have m
variables. But since x0 ∈ X − , which is a contradiction.
Define {x(j) }j∈Z to be the test resulting changing the
j th bit of x0 to a 1. By the minimal definition of x0 ,
∀j ∈ Z : x(j) ∈ X + .
Suppose |Z| > m. Take a subset Z 0 ⊆ Z such
that |Z 0 | = m + 1. Then, from the definition
of X + and X − , Prh∈V [h(x0 ) = 0 ∧ ∀j ∈ Z 0 :
h(x(j) ) = 1] > 1 − (m + 1)q ≥ 0, which means
Prh∈V [h includes variables Z 0 ] > 0. Therefore, there
is a disjunction with at least m + 1 variables, which is
a contradiction.
Thus, |Z| = m, so there is only one hypothesis such
that h(x0 ) = 0, the hypothesis with variables at Z.
So 1/|V | > 1 − q (by definition of X − ), which implies
|V | = 1 since q ≤ 1/2, which is a contradiction. Thus,
by contradiction, the problem with l = 1 is (m + 1)split-neighborly. For l > 1, we proceed by induction.
We can define the graph as above, define X − and X +
as above, and x0 and Z as above. The same argument
goes through that |Z| = m. Thus, (1 − q) proportion
of the hypotheses have a disjunction with variables at
the indices Z. These hypotheses are simply another
copy of the problem with l − 1 conjunctions and d − m
variables. Since that problem has 1/2 coherence and
is m + 1 + 3(l − 2)-splittable (by induction hypothesis), there exists some test with a split constant of
1
m+1+3(l−2)+2 for a total split constant on the original
problem of

The test graph has an edge from x to x0 if ||x−x0 ||1 = 1
(the bit strings differ in one location).
Let x+ be the value of x or x0 with more 1’s (and let

(1 − q)

1
1
=
m + 1 + 3(l − 2) + 2
m + 1 + 3(l − 1)

Stephen Mussmann, Percy Liang

Thus, the problem is m + 1 + 3(l − 1)-split-neighborly
by induction.
6.5

Box Object Localization

Theorem 4.3. The object localization problem where
S is a box is 4-split-neighborly.
Notationally, refer to zh as the integer vector for the
hypothesis h and zh,i to be its ith component.
We begin by fixing two tests x and x0 such that ||x −
x0 ||1 = 1. Without loss of generality, let x0 − x = e1
where e1 is the 1st elementary vector. Since the box
is axis symmetric, there exists radii ri ≥ 0 such that
x − zh ∈ S ↔ ∀i : |xi − zh,i | ≤ ri . Without loss of
generality, assume x = (r1 , 0, 0, ..., 0) and x0 = (r1 +
1, 0, 0, ..., 0). Recall ∆(x, x0 ) = {h : h(x) = 0 ∧ h(x0 ) =
1}, this implies that ∆(x, x0 ) = {h : zh,1 = 0 ∧ ∀i >
1 : |zh,i | ≤ ri }. We will begin by fixing a subset V ⊆
∆(x, x0 ). As in all the application proofs, we will start
by assuming by contradiction that there is no test with
a split constant in the range [q, 1 − q] where q = 1/4.
We will use this contradiction to show that the size of
V is small, so that there is in fact a test with a split
constant q which is a contradiction.
6.5.1

Majority Element

6.5.2

Side Splits

Intuitively, we will create a sequence of tests that each
remove at least half of the elements with the ith component not equal to m. For each test in the sequence,
the probability that the test yields 1 over the hypotheses in V must be greater that 1 − q so we can prove
that there aren’t many elements that disagree with m
at any component.
Here we recursively define sets Si , Bi , and Ai . Si will
be defined in terms of Bi and Bi will be defined in
terms of Si−1 .
Define S0 = V and for i > 1, Si = Si−1 − Bi . Noting that we could reflect the ith component about mi ,
without loss of generality, suppose that
Pr [zh,i > mi ] ≥ Pr [zh,i < mi ]

h∈Si

h∈Si

Define Bi = {h ∈ Si−1 : zh,i > mi } and Ai = {h ∈
Si−1 : zh,i < mi }
Note that |Bi | ≥ |Ai |.
Further, there is a test x(i) = (−r1 , ..., −ri , 0, ...0) such
that h(x(i) ) = 1 ↔ h ∈ Si and thus by the contradiction assumption,

Fix a dimension i. Examine the tests Xi = {jei :
j = 0, .., 2ri + 1} and note that for h ∈ V ⊆ ∆(x, x0 ),
h(jei ) = 1[zh,i ≥ j − ri ].
By the contradiction assumption,
Eh∈V [h(jei )] 6∈ [q, 1 − q]

Pr [zh,i ≥ j − ri ] 6∈ [q, 1 − q]

h∈V

|Si |
6∈ [q, 1 − q]
|S|
However, since Prh∈V [zh,i = mi ] > 1 − 2q, |Bi |/|V | <
2q. We now prove by induction that |Si |/|V | > 1 − q.
The base case is that |S1 |/|V | = 1 > 1 − q. As long as
q ≤ 1/4, since |Si−1 |/|V | > 1 − q and |Bi |/|V | < 2q,
|Si |/|S| > 1 − 3q ≥ q (since q = 1/4)and thus by the
contradiction assumption |Si |/|S| > 1 − q.
Note that the Bi are disjoint because

Since Prh∈V [zh,i ≥ −ri ] = 1 and Prh∈V [zh,i ≥ ri +1] =
0, there must be some integer mi such that

Bi ⊆ Si = V − B1 − B2 − ... − Bi−1

Pr [zh,i ≥ mi ] > 1 − q

h∈V

|Sd | > (1 − q)|V |

Pr [zh,i ≥ mi + 1] < q

h∈V

|V −
which implies that
Pr [zh,i = mi ] > 1 − 2q

h∈V

d
G

Bi | > (1 − q)|V |

i=1

|V | −

d
X

|Bi | > (1 − q)|V |

i=1

Define thus, there exists a vector m such that there is
a 1 − 2q probability that an hypothesis’ ith component
matches m.

q|V | >

d
X
i=1

|Bi |

Generalized Binary Search For Split-Neighborly Problems

Define the set of elements M 0 ⊆ V as the points with
a component not equal to m. This is the union of all
Ai and Bi ,

|M 0 | = |

d
[

Ai ∪

i=1

≤

d
X

d
[

Bi |

i=1

|Ai | +

i=1

d
X

zh ∈ S} and since S is bounded, there exists some
B ∈ Z such that ±Bei ∈ X − . Thus there exists some
c1 ≤ 0, c2 ≥ 0 such that (c1 − 1)ei ∈ X − , c1 ei ∈ X + ,
c2 ei ∈ X + , (c2 + 1)ei ∈ X − . From the definition of
X + and X − ,
Pr [h((c1 − 1)ei ) = 0, h(c1 ei ) = 1, ...

h∈V

|Bi |

h(c2 ei ) = 1, h((c2 + 1)ei ) = 0] > 1 − 4q

i=1

≤2

d
X

Define Sl = {s−i : si = l, s ∈ S} to be the slices of
S along axis i at location l. Therefore, h(jei ) = 1 ↔
zh,−i ∈ Szh,i −j .

|Bi |

i=1

< 2q|V |
0

Also note that |M | ≥ |V | − 1 since there can only be
one element that doesn’t disagree with any element of
m. Thus,

Note that S−l = Sl since the shape S is axis symmetric. Combining these three facts,
Pr [zh,−i ∈ S|zh,i −c1 | ∩ S|zh,i −c2 | \ ...

h∈V

\(S|zh,i −(c1 −1)| ∪ S|zh,i −(c2 +1)| )] > 1 − 4q

|V | − 1 < 2q|V |
1
1 − 2q

Since q ≤ 1/3, then this implies |V | < 3 so there is
a test with a split of 1/3, which is a contradiction.
So in a proof by contradiction, the problem is 4-splitneighborly.

Note that for l0 > l ≥ 0, Si,l0 ⊆ Si,l because of axisconvexity. To see this, suppose there was t ∈ Si,l0 \
Si,l , then there would be three elements s(−1) , s(0) , s(1)
(j)
(−1)
(0)
(1)
such that s−i = t and si
= −l0 , si = l, si = l0 ,
which would imply s(−1) ∈ S, s(0) 6∈ S, s(1) ∈ S which
contradicts axis-convexity.

6.6

Thus, in order for the set composed of slices of S in
the equation above to be non-empty,

|V | <

Convex, axis-symmetric Shape Object
Localization

Theorem 4.4. If S is a bounded, axis-symmetric,
axis-convex shape, the object localization problem is
(4d + 1)-split-neighborly.
0

Proof. Let the test graph has an edge from x to x if
||x − x0 ||1 = 1.
Fix a subset V ⊆ ∆(x, x0 ). Without loss of generality,
let x0 = 0d . V ⊆ ∆(x, x0 ) ⊆ {h : h(x0 ) = 1} = {h :
zh − x0 ∈ S} = {h : zh ∈ S}
For a proof by contradiction, the problem is not 4d+1split-neighborly so that |V | > 1 and there is no test x
such that Eh∈V [h(x)] ∈ [q, 1−q], where q = 1/(4d+1).

|zh,i − c1 |, |zh,i − c2 | < |zh,i − c1 + 1|, |zh,i − c2 − 1|
it must be the case that zh,i =
define to be mi . So,

c1 +c2
2

∈ Z which we

Pr [zh,i = mi ] > 1 − 4q

h∈V

Repeating this argument for all dimensions and combining,
Pr [∀i : zh,i = mi ] > 1 − 4dq

h∈V

Let

There is only one such element zh = m so
X + = {x ∈ X : Pr [h(x) = 1] > 1 − q}
h∈V

X

−

= {x ∈ X : Pr [h(x) = 1] < q} = X − X +
h∈V

Note that x0 = 0d ∈ X + since V ⊆ {h : h(x0 ) = 1}.
Fix a dimension i. Examine the set of tests {jei : j ∈
Z}. From above, 0ei ∈ X + . Further, since V ⊆ {h :

1
1
1
> 1 − 4dq = 1 − 4d
=
|V |
4d + 1
4d + 1
So |V | < 4d + 1 so there must be a split of at least q
which is a contradiction.

Stephen Mussmann, Percy Liang

6.7

Discrete Binary Linear Classifiers

Theorem 4.5. The discrete binary linear classifier
problem is max(16, 8r)-split-neighborly.
1
1
, 8r
)
Define q = min( 16

Recall that for the Discrete Binary Linear Classifier
case, we have hypotheses as a pair of vectors and
threshold h = (wh , bh ) ∈ {−1, 0, 1}d × Z and tests
as vectors {0, 1}d . Recall h(x) = 1[wh · x > bh ].
From the problem setting of Discrete Binary Linear
Classifiers, we know that,
(+)
wh
(−)

wh

−b≤

(−)
r(wh
(+)

+ b ≤ r(wh

Note that h(x(0) ) = 0 implies that 0 ≤ bh . Further
note that, h(x(1) ) = 1 implies that wh,1 > bh . Thus,
the only possibility is that wh,1 = 1 and bh = 0.
Let T+− denote the number of flips from positive to
negative weights and let T−+ denote the number of
flips from negative to positive. Then, the weights for
the new (reduction) problem will be
(+)
wnew
= w(+) + T−+ − T+−

d
+ b) −
8

− b − 1) −

(−)
wnew
= w(−) + T+− − T−+

d
8

Recall w(+) is the number of positive elements of w and
w(−) is the number of negative elements. Notationally
wh,i refers to the ith component of wh .
6.7.1

flip the 0’s and 1’s of the test so long as we flip the nonzero entries of wh at that same position, and change
bh accordingly. We flip the bits so that x becomes x(0)
and x0 becomes x(1) .

0 = bnew = b − T+− + T−+
From the last equation, b = T+− − T−+ . Thus,
(+)
wnew
= w(+) − b
(−)
wnew
= w(−) + b

Key Lemma and its Sufficiency

We will first state a lemma and then prove that it
implies the problem stated stated.

Since,

Lemma 6.3. Define

w(+) − b ≤ r(w(−) + b) −

x(0) = (0, 0, ..., 0)
x

(1)

H = {h ∈ H : h(x(0) = 0 ∧ h(x(1) ) = 1 ∧ ...
(+)

∧wh

(−)

... ∧ wh

(+)

≤ r(wh

1
(+)
(−)
wnew
≤ rwnew
− d
8

d
− 1) − }
8

Proof of Theorem 4.5 from Lemma 6.3

We will prove Theorem 4.5 by a reduction to Lemma
6.3. To show that the problem is 1/α-split-neighborly,
we need to show that for two tests with x and x0 with
||x − x0 ||1 = 1 that for any subset V ⊆ ∆(x, x0 ) = {h :
h(x) = 0 ∧ h(x0 ) = 1}, that |V | ≤ 1 or there exists a
test x̂ such that
Pr [h(x̂) = 1] ∈ [q, 1 − q]

h∈V

Note that by permuting the indices of x and x0 , we can
make the first index the one that is different between x
and x0 . Additionally, for the remaining indices we can

d
8

then,

d
(−)
≤ rwh − ∧ ...
8

For any subset V ⊂ H 0 , there exists a test x such that
Eh∈V [h(x)] ∈ [q, 1 − q]
6.7.2

w(−) + b ≤ r(w(+) − b − 1) −

= (1, 0, ..., 0)

0

d
8

1
(−)
(+)
wnew
≤ r(wnew
− 1) − d
8
We can see that the hypothesis conditions for the original theorem imply that ∆(x(0) , x(1) ) is a subset of the
(−)
hypotheses that satisfy the conditions based on wnew
(+)
and wnew so Lemma 6.3 implies the binary linear classifier is 1/q-split-neighborly which means max(16, 8r)split-neighborly.
6.7.3

Proof of Lemma 6.3

The remainder of this is devoted to proving Lemma
6.3
We begin by fixing a subset V ⊆ H 0 . As in all the
application proofs, we will start by assuming by contradiction that there is no test with a split constant in
the range [q, 1 − q]. We will use this contradiction to
show that the size of V is small.

Generalized Binary Search For Split-Neighborly Problems

Recall that bh = 0 for all hypotheses in the reduced
problem and wh,1 = 1. This follows from the fact that
h(x(0) ) = 0 and h(x(1) ) = 1.

6.7.5

Ratio between m(−) and m(+)

Note,
(+)

6.7.4

Eh∈V [wh ] =

Majority Vector

d
X

Pr[wh,i = 1]

i=1

Let ei be an elementary vector with all entries 0 except
for the ith entry which is 1.
Lemma 6.4. There exists a vector m ∈ {−1, 0, 1}d
such that ∀i : mi = 0 : Prh∈V [wh,i = mi ] ≥ 1 − 2q and
∀i : mi 6= 0 : Prh∈V [wh,i = mi ] ≥ 1 − q

≤ (q)(d − m(+) ) + (1)m(+) = qd + (1 − q)m(+)
m(+) ≥

1
(+)
(Eh∈V [wh ] − qd)
1−q

Further note,
Proof. By the contradiction assumption, there isn’t a
test with a split constant greater than q,

(+)

Eh∈V [wh ] =

d
X

Pr[wh,i = 1]

i=1

Pr [wh · ei > bh ] 6∈ [q, 1 − q]

h∈V

≥ (0)(d − m(+) ) + (1 − q)m(+) = (1 − q)m(+)
m(+) ≤

Pr [wh,i > 0] 6∈ [q, 1 − q]

h∈V

Pr [ws,i = 1] 6∈ [q, 1 − q]

h∈V

Also, by the contradiction assumption,

1
(+)
Eh∈V [wh ]
1−q
(−)

We have similar equations for m(−) and Eh∈V [wh ]
Let m̄ be the vector of m without the first component.
Recall that we have

Pr [wh · (e0 + ei ) > bh ] 6∈ [q, 1 − q]

(+)

h∈V

Pr [1 + wh,i > 0] 6∈ [q, 1 − q]

h∈V

Pr [wh,i 6= −1] 6∈ [q, 1 − q]

h∈V

∀h ∈ V : wh

(−)

≤ rwh

(+)

1
− d
8

(−)

Eh∈V [wh ] ≤ rEh∈V [wh ] − qrd
1
1
(+)
(−)
Eh∈V [wh ] ≤ r
(Eh∈V [wh ] − qd)
1−q
1−q

Pr [wh,i = −1] 6∈ [q, 1 − q]

m(+) ≤ rm(−)

h∈V

m̄(+) ≤ rm̄(−)

Since Prh∈V [wh,i = 1] + Prh [wh,i = 0] + Prh [wh,i =
1] = 1,
Also, recall,
Pr [wh,i = 0] 6∈ [q, 1 − 2q]

h∈V

(−)

∀h ∈ V : wh

Thus, each index is either mostly 1, mostly 0, or mostly
−1 for elements in S (since q < 1/3). Define m ∈
{−1, 01}d such that

(−)

(+)

≤ r(wh

(+)

Eh∈V [wh ] ≤ rEh∈V [wh ] − qrd − r
1
1
r
(−)
(+)
Eh∈V [wh ] ≤ r
(Eh∈V [wh ] − qd) −
1−q
1−q
1−q

mi = argmax Pr [wh,i = c]
c

h∈V

1
− 1) − d
8

m(−) ≤ rm(+) −

r
1−q

m(−) ≤ r(m(+) − 1)
Note that m1 = 1.

m̄(−) ≤ rm̄(+)

Stephen Mussmann, Percy Liang

6.7.6

Partition

Let w̄ be the vector of w without the first component.
Definition 6.1. Let
• X

+

= {x : Prh∈V [w¯h · x ≥ 1] > 1 − q}

Proof. We prove this by induction on the number of
1’s in x for x ∈ X ∗ .
The base case is x = 0d which is trivially in X 0 .
For other x, suppose xi = 1 at a location where
mi = 0. Then we know x − ei ∈ X 0 by the induction hypothesis.

• X 0 = {x : Prh∈V [w¯h · x = 0] > 1 − 2q}
• X − = {x : Prh∈V [w¯h · x ≤ −1] > 1 − q}

P rh∈V [wh · (x − ei ) = 0] > 1 − 2q

Lemma 6.5. X + , X 0 , X − is a partition of {0, 1}d−1
Proof. Since q ≤ 1/4 and the three defining events
are mutually exclusive. It is clear that A+ , A0 , A− are
disjoint. Next we show that every point is in at least
one of the sets. Suppose a point x is in neither A+ or
A− .
Using the contradiction assumption on the test (0, x),
Pr [wh · (0, x) > 0] 6∈ [q, 1 − q]

h∈V

P rh∈V [wh,i = 0] > 1 − 2q
From these,
P rh∈V [wh · x = 0] > 1 − 4q ≥ q
for q ≤ 1/5. So x 6∈ X + ∪ X − and thus x ∈ X 0 .
The only other case is where xi = xj = 1 at locations
where mi = 1 and mj = −1. Then we know x − ei −
ej ∈ X 0 from the induction hypothesis.

Pr [w¯h · x > 0] 6∈ [q, 1 − q]

h∈V

P rh∈V [wh · (x − ei − ej ) = 0] > 1 − 2q

Pr [w¯h · x > 0] < q

P rh∈V [wh,i = 1] > 1 − q

h∈V

Using the contradiction assumption on the test (1, x),
Pr [wh · (1, x) > 0] 6∈ [q, 1 − q]

P rh∈V [wh,j = −1] > 1 − q
From these,

h∈V

P rh∈V [wh · x = 0] > 1 − 4q ≥ q

Pr [1 + w¯h · x > 0] 6∈ [q, 1 − q]

h∈V

Pr [w¯h · x ≥ 0] 6∈ [q, 1 − q]

h∈V

and similarly, x ∈ X 0 .

Pr [w¯h · x < 0] < q

h∈V

6.7.7

Combining these,

Probability Distribution

We now define a probability distribution over x ∈ X ∗ .
Pr [w¯h · x = 0] = 1 − Pr [w¯h · x > 0] − Pr [w¯h · x < 0]

h∈V

h∈V

Without loss of generality, suppose m̄(+) ≥ m̄(−) .

h∈V

> 1 − 2q
Thus, x 6∈ X + and x 6∈ X − imply x ∈ X 0 so the three
sets are a partition.
Definition 6.2. Define X ∗ to be every x ∈ {0, 1}d
that (m̄ = 1) · x = (m̄ = −1) · x, where (m̄ = 1) is the
element-wise boolean function.

• Randomly draw an injection f : {i : m̄i = −1} →
{i : m̄i = 1}.
• Initialize x = 0d−1
• For indices {i
bernoulli(1/2).

:

m̄i

≤

0}, draw xi

∼

• For {i : m̄i = −1}, set xf (i) = xi
Intuitively, this means that there are as many ones of
x in positions where m̄ = 1 as there are places where
m̄ = −1.
Lemma 6.6. X ∗ ⊆ X 0

Note that the result x ∈ X ∗ because of the pairing
f , there will be a 1 where m̄i = 1 for each 1 where
m̄i = −1.

Generalized Binary Search For Split-Neighborly Problems

6.7.8

Set T

Definition 6.3. For the probability distribution,

unless ∀i : m̄i = 0 : wt,i = 0 and ∀i : m̄i = −1 :
wt,i + wt,f (i) = 0, call this condition(t, f ).

Q(h) = Pr ∗ [wh · x = 0]

Ef [1[condition(t, f )] + ...

x∈X

1
1 1
(1 − 1[condition(t, f )])] > 1 − min( , )
2
4 2r

Lemma 6.7. Let T = {h ∈ V : Q(h) > 1 − 4q}, then
|V | > 5|T |.

1 1
Pr[condition(t, f )] > 1 − min( , )
f
2 r

Proof. For x ∈ X ∗ , since X ∗ ⊆ X 0 ,
Pr [wh · x = 0] > 1 − 2q

h∈V

P

1[wh · x = 0]
> 1 − 2q
|V |
P
X
1[wh · x = 0]
> 1 − 2q
P (x) h∈V
|V |
x∈X 0
P
P
h∈V
x∈X 0 P (x)1[wh · x = 0]
> 1 − 2q
|V |
P
h∈V Q(h)
> 1 − 2q
|V |
h∈V

If m̄(−) = 0, then m̄(+) = 0, and thus ∀i : m̄i = 0 :
wt,i = 0 so t = 0d and |T | = 1 ≤ 3.
Note that Prf [condition(t, f )] > 1/2 implies that ∀i :
mi = 0 : wt,i = 0.
Lemma 6.9. If there exists i, j such that m̄i = m̄j =
−1, then wt,i = wt,j .
Proof. Prf [condition(t, f )] >

1
2

means that

Pr[wt,i = −wt,f (i) ] >

1
2

Pr[wt,j = −wt,f (j) ] >

1
2

f

|T |
|V | − |T |
(1) +
(1 − 4q) > 1 − 2q
|V |
|V |

f

so
2|T | > |V |
{l : m̄l = 1 ∧ wt,l = −wt,i }
> 1/2
{l : m̄l = −1}
{l : m̄l = 1 ∧ wt,l = −wt,j }
> 1/2
{l : m̄l = −1}

Lemma 6.8. |T | ≤ 3
Proof. Recall that m̄(+) ≤ rm̄(−) and m̄(−) ≤ rm̄(+)
as well
1
1
1
) since q ≤ min( 16
, 8r
)
Also 1 − 4q ≥ 1 − min( 41 , 2r
1
For any t ∈ T , Q(t) > 1 − 4q ≥ 1 − min( 41 , 2r
). Define
Ber(1/2) to be a Bernoulli random variable.

Thus, there is some c ∈ {−1, 0, 1} such that ∀i : m̄i =
1 : wt,i = c.
Pr[condition(t, f )] >

1 1
Pr ∗ [wt · x = 0] > 1 − min( , )
x∈X
4 2r
X
Ef [Pr[
wt,i Ber(1/2) + ...

f

1
r

Pr[∀i : m̄i = −1 : wt,f (i) = −c] > 1 −
f

i:mi =0

1 1
(wt,i + wt,f (i) )Ber(1/2) = 0]] > 1 − min( , )
4 2r
=−1

X
i:mi

which is only possible if wt,i = wt,j .

1
r

1 − Pr[∃i : m̄i = −1 : wt,f (i) 6= −c] > 1 −
f

Pr[∃i : m̄i = −1 : wt,f (i) 6= −c] <
f

1
r

1
r

Note that
Suppose ∃j : m̄j = 1 : wt,j 6= −c,
Pr[

X

wt,i Ber(1/2) + ...
Pr[∃i : m̄i = −1 : f (i) = j] =

i:m̄i =0

X

(wt,i + wt,f (i) )Ber(1/2) = 0] ≤

i:m̄i =−1

1
2

f

1
r

which is a contradiction. So ∀j : m̄j = 1 : wt,j = −c.

Stephen Mussmann, Percy Liang

Thus, c completely determines t. Since there are three
options for c, there are three options for t, and |T | ≤
3.
Since |T | ≤ 3 and 2|T | ≥ |V |, |V | ≤ 6. Thus, there
is a split of 1/6 which is a contradiction since q ≤ 18 .
Thus, the lemma is proved. And thus the binary linear
classifier problem is split-neighborly.

