JMLR: Workshop and Conference Proceedings vol 30 (2013) 1–29

Active and passive learning of linear separators
under log-concave distributions
Maria Florina Balcan

NINAMF @ CC . GATECH . EDU

Georgia Institute of Technology

Philip M. LongPLONG @ MICROSOFT. COM

Microsoft

Abstract
We provide new results concerning label efficient, polynomial time, passive and active learning of
linear separators. We prove that active learning provides an exponential improvement over PAC(passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constantfactor) sample complexity for such problems. This resolves an open question of (Long, 1995,
2003; Bshouty et al., 2009) concerning the sample complexity of efficient PAC algorithms under
the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time
PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a generaland natural class of data-distributions, providing significant progress towards a longstanding open
question of (Ehrenfeucht et al., 1989; Blumer et al., 1989).
We also provide new bounds for active and passive learning in the case that the data might not
be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To
derive our results, we provide new structural results for (nearly) log-concave distributions, whichmight be of independent interest as well.
Keywords: Active learning, PAC learning, ERM, nearly log-concave distributions, Tsybakov lownoise condition, agnostic learning.

1. Introduction
Learning linear separators is one of the central challenges in machine learning. They are widelyused and have been long studied both in the statistical and computational learning theory. A seminal
result of (Blumer et al., 1989), using tools due to (Vapnik and Chervonenkis, 1971), showed that ddimensional linear separators can be learned to accuracy 1 − ǫ with probability 1 − δ in the classic
PAC model in polynomial time with O((d/ǫ) log(1/ǫ)+ (1/ǫ) log(1/δ)) examples. The best known
lower bound for linear separators is Ω(d/ǫ+(1/ǫ) log(1/δ)), and this holds even in the case in which
the distribution is uniform (Long, 1995). Whether the upper bound can be improved to matchthe lower bound via a polynomial-time algorithm is been long-standing open question, both forgeneral distributions (Ehrenfeucht et al., 1989; Blumer et al., 1989) and for the case of the uniform
distribution in the unit ball (Long, 1995, 2003; Bshouty et al., 2009). In this work we resolve thisquestion in the case where the underlying distribution belongs to the class of log-concave and nearlylog-concave distributions, a wide class of distributions that includes the gaussian distribution anduniform distribution over any convex set, and which has played an important role in several areas
including sampling, optimization, integration, and learning (Lovasz and Vempala, 2007).
We also consider active learning, a major area of research of modern machine learning, where
the algorithm only receives the classifications of examples when it requests them (Dasgupta, 2011).

c 2013 M.F. Balcan & P.M. Long.

BALCAN L ONG

Our main result here is a polynomial-time active learning algorithm with label complexity that is
exponentially better than the label complexity of any passive learning algorithm in these settings.
This answers an open question in (Balcan et al., 2007) and it also significantly expands the setof cases for which we can show that active learning provides a clear exponential improvement in
1/ǫ (without increasing the dependence on d) over passive learning. Remarkably, our analysis forpassive learning is done via a connection to our analysis for active learning – to our knowledge, thisis the first paper using this technique.
We also study active and passive learning in the case that the data might not be linearly separable. We specifically provide new improved bounds for the widely studied Tsybakov low-noise
condition (Mammen and Tsybakov, 1999; Bartlett et al., 2005; Massart and Nedelec, 2006), as well
as new bounds on the disagreement coefficient, with implications for the agnostic case (i.e., arbitrary
forms of noise).
Passive Learning In the classic passive supervised machine learning setting, the learning algorithm
is given a set of labeled examples drawn i.i.d. from some fixed but unknown distribution over the
instance space and labeled according to some fixed but unknown target function, and the goal is to
output a classifier that does well on new examples coming from the same distribution. This setting
has been long studied in both computational learning theory (within the PAC model (Valiant, 1984;
Kearns and Vazirani, 1994)) and statistical learning theory (Vapnik, 1982, 1998; Boucheron et al.,2005), and has played a crucial role in the developments and successes of machine learning.
However, despite remarkable progress, the basic question of providing polynomial-time algorithms with tight bounds on the sample complexity has remained open. Several milestone results
along these lines that are especially related to our work include the following. The analysis of(Blumer et al., 1989), proved using tools from (Vapnik and Chervonenkis, 1971), implies that linear separators can be learned in polynomial time with O((d/ǫ) log(1/ǫ) + (1/ǫ) log(1/δ)) labeled
examples. (Ehrenfeucht et al., 1989) proved a bound that implies an Ω(d/ǫ + (1/ǫ) log(1/δ)) lower
bound for linear separators and explicitly posed the question of providing tight bounds for this class.
(Haussler et al., 1994) established an upper bound of O((d/ǫ) log(1/δ)), which can be achieved inpolynomial-time for linear separators.
(Blumer et al., 1989) achieved polynomial-time learning by finding a consistent hypothesis (i.e.,a hypothesis which correctly classifies all training examples); this is a special case of ERM (Vapnik,
1982). An intensive line of research in the empirical process and statistical learning theory literature
has taken account of “local complexity” to prove stronger bounds for ERM (van der Vaart and Wellner,
1996; van de Geer, 2000; Bartlett et al., 2005; Long, 2003; Mendelson, 2003; Giné and Koltchinskii,
2006; Hanneke, 2007; Hanneke and Yang, 2012). In the context of learning, local complexity
takes account of the fact that really bad classifiers can be easily discarded, and the set of “local” classifiers that are harder to disqualify is sometimes not as rich. A recent landmark result of(Giné and Koltchinskii, 2006) (see also (Raginsky and Rakhlin, 2011; Hanneke and Yang, 2012)) is
the bound for consistent algorithms ofO((d/ǫ) log(cap(ǫ)) + (1/ǫ) log(1/δ))(1)

where cap(ǫ) is the Alexander capacity, which depends on the distribution (Alexander., 1987) (seeSection 8 and Appendix A for further discussion). However, this bound can be suboptimal for linear
separators.
In particular, for linear separators in the case in which the underlying distribution
is uniform
d+log(1/δ), whenin the unit ball, the sample complexity is known (Long, 1995, 2003) to be Θ
ǫ
2

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

computational considerations are ignored. (Bshouty et al., 2009), using the doubling dimension(Assouad, 1983), another measure of local complexity, proved a bound ofpO((d/ǫ) log(1/ǫ) + (1/ǫ) log(1/δ))(2)√√
for a polynomial-time algorithm. As a lower bound of Ω( d) on cap(ǫ) for ǫ = o(1/ d) for thecase of linear separators and the uniform distribution is implicit in (Hanneke, 2007), the bound of(Giné and Koltchinskii, 2006) given by (1) cannot yield a bound better thanO((d/ǫ) min{log d, log(1/ǫ)} + (1/ǫ) log(1/δ))(3)

in this case.
In this paper we provide a tight bound (up to constant factors) on the sample complexity ofpolynomial-time learning of linear separatorswith respect to log-concave distributions. Specifi
d+log(1/δ)
using a polynomial-time algorithm that holds forcally, we prove an upper bound of Oǫany zero-mean log-concave distribution. We also prove an information theoretic lower bound thatmatches our (computationally efficient) upper bound for each log-concave distribution. This provides the first bound for a polynomial-time algorithm that is tight for an interesting non-finite class ofhypothesis functions under a general class of data-distributions, and also characterizes (up to a constant factor) the distribution-specific sample complexity for each distribution in the
p class. In the special case of the uniform distribution, our upper bound closes the existing Ω(min{ log(1/ǫ), log(d)})
gap between the upper bounds (2) and (3) and the lower bound of (Long, 1995).
Active Learning We also study learning of linear separators in the active learning model; here thelearning algorithm can access unlabeled (i.e., unclassified) examples and ask for labels of unlabeled
examples of its own choice, and the hope is that a good classifier can be learned with significantly
fewer labels by actively directing the queries to informative examples. This has been a major areaof machine learning research in the past fifteen years mainly due the availability of large amounts
of unannotated or raw data in many modern applications (Dasgupta, 2011), with many exciting
developments on understanding its underlying principles as well (Freund et al., 1997; Dasgupta,
2005; Balcan et al., 2006, 2007; Hanneke, 2007; Dasgupta et al., 2007; Castro and Nowak, 2007;
Balcan et al., 2008; Koltchinskii, 2010; Beygelzimer et al., 2010). However, with a few exceptions (Balcan et al., 2007; Castro and Nowak, 2007; Dasgupta et al., 2005), most of the theoreticaldevelopments have focused on the so called disagreement-based active learning paradigm (Hanneke,2011; Koltchinskii, 2010); methods and analyses developed in this context are often suboptimal, as
they take a conservative approach and consider strategies that query even points on which there
is a small amount of uncertainty (or disagreement) among the classifiers still under consideration
given the labels queried so far. The results derived in this manner often show an improvement in
the 1/ǫ factor in the label complexity of active versus passive learning; however, unfortunately, thedependence on the d term typically gets worse.
By analyzing a more aggressive, margin-based active learning algorithm, we prove that we canefficiently (in polynomial time) learn homogeneous linear separators when the underlying distribution is log-concave by using only O((d + log(1/δ) + log log(1/ǫ)) log(1/ǫ)) label requests, answering an open question in (Balcan et al., 2007). This represents an exponential improvement of active
learning over passive learning and it significantly broadens the cases for which we can show that thedependence on 1/ǫ in passive learning can be improved to only Õ(log(1/ǫ)) in active learning, but
without increasing the dependence on the dimension d. We note that an improvement of this typewas known to be possible only for the case when the underlying distributions is (nearly) uniform
3

BALCAN L ONG

in the unit ball (Balcan et al., 2007; Dasgupta et al., 2005; Freund et al., 1997); even for this special case, our analysis improves by a multiplicative log log(1/ǫ) factor the results of (Balcan et al.,2007); it also provides better dependence on d than any other previous analyses implementable in
a computationally efficient manner (both disagreement-based (Hanneke, 2011, 2007) and more aggressive ones (Dasgupta et al., 2005; Freund et al., 1997)), and over the inefficient splitting index
analysis of (Dasgupta, 2005).
Techniques At the core of our results is a novel characterization of the region of disagreementof two linear separators under a log-concave measure. We show that for any two linear separators
specified by normal vectors u and v, for any constant c ∈ (0, 1) we can pick a margin as small asγ = θ(α), where α is the angle between u and v, and still ensure that the probability mass of theregion of disagreement outside of band of margin γ of one of them is cα (Theorem 4). Using thisfact, we then show how we can use a margin-based active learning technique, where in each round
we only query points near the hypothesized decision boundary, to get an exponential improvement
over passive learning.
We then show that any passive learning algorithm that outputs a hypothesis consistent withO(d/ǫ + (1/ǫ) log(1/δ)) random examples will, with probability at least 1 − δ, output a hypothesisof error at most ǫ (Theorem 6). Interestingly, our analysis is quite dissimilar to the classic analyses
of ERM. It proceeds by conceptually running the algorithm online on progressively larger chunks ofexamples, and using the intermediate hypotheses to track the progress of the algorithm. We show,
using the same tools as in the active learning analysis, that it is always likely that the algorithm
will receive informative examples. Our analysis shows that the algorithm would also achieve 1 − ǫaccuracy with high probability even if it periodically built preliminary hypotheses using some of theexamples, and then only used borderline cases for those preliminary classifiers for further training.1
To achieve the optimal sample complexity, we have to carefully distribute the confidence parameter,by allowing higher probability of failure in the later stages, to compensate for the fact that, once thehypothesis is already pretty good, it takes longer to get examples that help to further improve it.
Non-separable case We also study label-efficient learning in the presence of noise. We showhow our results for the realizable case can be extended to handle (a variant of) the Tsybakovnoise, which has received substantial attention in statistical learning theory, both for passive andactive learning (Mammen and Tsybakov, 1999; Bartlett et al., 2005; Massart and Nedelec, 2006;
Giné and Koltchinskii, 2006; Balcan et al., 2007; Koltchinskii, 2010; Hanneke, 2011); this includes
the random classification noise commonly studied in computational learning theory (Kearns and Vazirani,1994), and the more general bounded (or Massart) noise (Bartlett et al., 2005; Massart and Nedelec,
2006; Giné and Koltchinskii, 2006; Koltchinskii, 2010). Our analysis for Massart noise leads tooptimal bounds (up to constant factors) for active and passive learning of linear separators whenthe marginal distribution on the feature vectors is log-concave, improving the dependence on d overprevious best known results. Our analysis for Tsybakov noise leads to bounds on active learningwith improved dependence on d over previous known results in this case as well.
We also provide a bound on the Alexander’s capacity (Alexander., 1987; Giné and Koltchinskii,2006) and the closely related disagreement coefficient notion (Hanneke, 2007), which have been
widely used to characterize the sample complexity of various (active and passive) algorithms (Hanneke,2007; Koltchinskii, 2010; Giné and Koltchinskii, 2006; Beygelzimer et al., 2010). This immediately
implies concrete bounds on the labeled data complexity of several algorithms in the literature, in1. Note that such examples would not be i.i.d from the underlying distribution!

4

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

cluding active learning algorithms designed for the purely agnostic case (i.e., arbitrary forms ofnoise), e.g., the A2 algorithm (Balcan et al., 2006) and the DHM algorithm (Dasgupta et al., 2007).
Nearly log-concave distributions We also extend our results both for passive and active learning to deal with nearly log-concave distributions; this is a broader class of distributions introducedby (Applegate and Kannan, 1991), which contains mixtures of (not too separated) log-concave distributions. In deriving our results, we provide new tail bounds and structural results for these distributions, which might be of independent interest and utility, both in learning theory and in otherareas including sampling and optimization.
We note that our bounds on the disagreement coefficient improve by a factor of Ω(d) over thebounds of (Friedman, 2009) (matching what was known for the much less general case of nearly
uniform distribution over the unit sphere); furthermore, they apply to the nearly log-concave casewhere we allow an arbitrary number of discontinuities, a case not captured by the (Friedman, 2009)
conditions at all. We discuss other related papers in Appendix A.

2. Preliminaries and Notation
We focus on binary classification problems; that is, we consider the problem of predicting a binary
label y based on its corresponding input vector x. As in the standard machine learning formulation,
we assume that the data points (x, y) are drawn from an unknown underlying distribution DXY
over X × Y ; X is called the instance space and Y is the label space. In this paper we assume thatY = {±1} and X = Rd ; we also denote the marginal distribution over X by D. Let C be the classof linear separators through the origin, that is C = {sign(w · x) : w ∈ Rd , kwk = 1}. To keep
the notation simple, we sometimes refer to a weight vector and the linear classifier with that weightvector interchangeably. Our goal is to output a hypothesis function w ∈ C of small error, whereerr(w) = errDXY (w) = P(x,y)∼DXY [sign(w · x) 6= y].
We consider two learning protocols: passive learning and active learning. In the passive learning
setting, the learning algorithm is given a set of labeled examples (x1 , y1 ), . . . , (xm , ym ) drawn
i.i.d. from DXY and the goal is output a hypothesis of small error by using only a polynomial
number of labeled examples. In the (pool-based) active learning setting, a set of labeled examples(x1 , y1 ) . . . (xm , ym ) is also drawn i.i.d. from DXY ; the learning algorithm is permitted direct accessto the sequence of xi values (unlabeled data points), but has to make a label request to obtain thelabel yi of example xi . The hope is that in the active learning setting we can output a classifierof small error by using many fewer label requests than in the passive learning setting by actively
directing the queries to informative examples (while keeping the number of unlabeled examples
polynomial). For added generality, we also consider the selective sampling active learning model,
where the algorithm visits the unlabeled data points xi in sequence, and, for each i, makes a decisionon whether or not to request the label yi based only on the previously-observed xj values (j ≤ i)and corresponding requested labels, and never changes this decision once made. Both our upperand lower bounds will apply to both selective sampling and pool-based active learning.
In the “realizable case”, we assume that the labels are deterministic and generated by a targetfunction that belongs to C. In the non-realizable case (studied in Sections 8 and 9) we do not makethis assumption and instead aim to compete with the best function in C.
Given two vectors u and v and any distribution D̃ we denote by dD̃ (u, v) = Px∼D̃ (sign(u·x) 6=
sign(v · x)); we also denote by θ(u, v) the angle between the vectors u and v.

5

BALCAN L ONG

3. Log-Concave Densities
Throughout this paper we focus on the case where the underlying distribution D is log-concave ornearly log-concave. Such distributions have played a key role in the past two decades in several
areas including sampling, optimization, and integration algorithms (Lovasz and Vempala, 2007),and more recently for learning theory as well (Kalai et al., 2005; Klivans et al., 2009b; Vempala,2010). In this section we first summarize known results about such distributions that are useful forour analysis and then prove a novel structural statement that will be key to our analysis (Theorem 4).
In Section 6 we describe extensions to nearly log-concave distributions as well.
Definition 1 A distribution over Rd is log-concave if log f (·) is concave, where f is its associateddensity function. It is isotropic if its mean is the origin and its covariance matrix is the identity.
Log-concave distributions form a broad class of distributions: for example, the Gaussian, Logistic, and uniform distribution over any convex set are log-concave distributions. The following lemma summarizes known useful facts about isotropic log-concave distributions (most arefrom (Lovasz and Vempala, 2007); the upper bound on the density is from (Klivans et al., 2009b)).
Lemma 2 Assume that D is log-concave in Rd and let f be its density function.
√(a) If D is isotropic then Px∼D [||X|| ≥ α d] ≤ e−α+1 . If d = 1 then: Px∼D [X ∈ [a, b]] ≤ |b−a|.
(b) If D is isotropic, then f (x) ≥ 2−7d 29d||x|| whenever 0 ≤ ||x|| ≤ 1/9. Furthermore, 2−7d ≤f (0) ≤ d(20d)d/2 , and f (x) ≤ A(d) exp(−B(d)||x||), where A(d) is 28d dd/2 e and B(d) is
2−7d, for all x of any norm.
2(d−1)(20(d−1))(d−1)/2(c) All marginals of D are log-concave. If D is isotropic, its marginals are isotropic as well.
(d) If E[kXk2 ] = C 2 , then P[||X|| ≥ RC] ≤ e−R+1 .
(e) If D is isotropic and d = 1 we have f (0) ≥ 1/8 and f (x) ≤ 1 for all x.
Throughout our paper we will use the fact that there exists a universal constant c such that theprobability of disagreement of any two homogeneous linear separators is lower bounded by the ctimes the angle between their normal vectors. This follows by projecting the region of disagreementin the space given by the two normal vectors, and then using properties of log-concave distributionsin 2-dimensions. The proof is implicit in earlier works (e.g., (Vempala, 2010)); for completeness,
we include a proof in Appendix B.
Lemma 3 Assume D is an isotropic log-concave in Rd . Then there exists c such that for any twounit vectors u and v in Rd we have cθ(v, u) ≤ dD (u, v).
To analyze our active and passive learning algorithms we provide a novel characterization of theregion of disagreement of two linear separators under a log-concave measure:
Theorem 4 For any c1 > 0, there is a c2 > 0 such that the following holds. Let u and v be two unit
vectors in Rd , and assume that θ(u, v) = α < π/2. If D is isotropic log-concave in Rd , then:
Px∼D [sign(u · x) 6= sign(v · x) and |v · x| ≥ c2 α] ≤ c1 α.

6(4)

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONSProof Choose c1 , c2 > 0. We will show that, if c2 is large enough relative to 1/c1 , then (4)holds. Let b = c2 α. Let E be the set whose probability we want to bound. Since the event underconsideration only concerns the projection of x onto the span of u and v, Lemma 2(c) implies wecan assume without loss of generality that d = 2.
Next, we claim that each member x of E has ||x|| ≥ b/α = c2 . Assume without loss ofgenerality that v · x is positive. (The other case is symmetric.) Then u · x < 0, so the angle ofx with u is obtuse, i.e. θ(x, u) ≥ π/2. Since θ(u, v) = α, this implies that θ(x, v) ≥ π/2 − α.
But x · v ≥ b, and v is unit length, so ||x|| cos θ(x, v) ≥ b, which, since θ(x, v) ≥ π/2 − α,implies ||x|| cos(π/2 − α) ≥ b; This, since cos(π/2 − α) ≤ α for all α ∈ [0, π/2], in turn implies||x|| ≥ b/α = c2 . This implies that, if B(r) is a ball of radius r in R 2 , that
P[E] =∞X
i=1

P[E ∩ (B((i + 1)c2 ) − B(ic2 ))].

(5)

To obtain the desired bound, we carefully bound each term in the RHS. Choose i ≥ 1.
Let f (x1 , x2 ) be the density of D. We haveZ
1E (x1 , x2 )f (x1 , x2 ) dx1 dx2 .
P[E ∩ (B((i + 1)c2 ) − B(ic2 ))] =(x1 ,x2 )∈B((i+1)c2 )−B(ic2 )Applying the density upper bound from Lemma 2 with d = 2, there are constants C1 and C2 suchthatZ
1E (x1 , x2 )C1 exp(−c2 C2 i) dx1 dx2
P[E ∩ (B((i + 1)c2 ) − B(ic2 ))] ≤(x1 ,x2 )∈B((i+1)c2 )−B(ic2 )Z
1E (x1 , x2 ) dx1 dx2 .
= C1 exp(−c2 C2 i)(x1 ,x2 )∈B((i+1)c2 )−B(ic2 )If we include B(ic2 ) in the integral again, we get
P[E ∩ (B((i + 1)c2 ) − B(ic2 ))] ≤ C1 exp(−c2 C2 i)

Z

1E (x1 , x2 ) dx1 dx2 .
(x1 ,x2 )∈B((i+1)c2 )Now, we exploit the fact that the integral above is a rescaling of a probability with respect to theuniform distribution. Let C3 be the volume of the unit ball in R 2 . Then, we have
P[E∩(B((i+1)c2 )−B(ic2 ))] ≤ C1 exp(−c2 C2 i)C3 (i+1)2 c22 α/π = C4 c22 α(i+1)2 exp(−c2 C2 i),
for C4 = C1 C3 /π. Returning to (5), we get
P[E] =∞
X
i=1

C4 c22 α(i + 1)2 exp(−c2 C2 i) = C4 c22 ×
2c C

4e2c2 C2 − 3ec2 C2 + 1(ec2 C2 − 1)3

× α.

c C

2 2 +1Since limc2 →∞ c22 × 4e 2 c2 −3e= 0, this completes the proof.
3(e 2 C2 −1)

We note that a weaker result of this type was proven (via different techniques) for the uniform
distribution in the unit ball in (Balcan et al., 2007). In addition to being more general, Theorem 4
is tighter and more refined even for this specific case – this improvement is essential for obtaining
tight bounds for polynomial time algorithms for passive learning (Section 5) and better bounds for
active learning as well.
7

BALCAN L ONG

4. Active Learning
In this section we analyze a margin-based algorithm for actively learning linear separators under logconcave distributions (Balcan et al., 2007) (Algorithm 1). Lower bounds proved in Section 7 showthat this algorithm needs exponentially fewer labeled examples than any passive learning algorithm.
This algorithm has been previously proposed and analyzed in (Balcan et al., 2007) for the special case of the uniform distribution in the unit ball. In this paper we analyze it for the much moregeneral class of log-concave distributions.
Algorithm 1 Margin-based Active Learning
Input: a sampling oracle for D, a labeling oracle, sequences mk > 0, k ∈ Z + (sample sizes) andbk > 0, k ∈ Z + (cut-off values).
Output: weight vector ŵs .
• Draw m1 examples from D, label them and put them in W (1).
• iterate k = 1, . . . , s– find a hypothesis ŵk with kŵk k2 = 1 consistent with all labeled examples in W (k).
– let W (k + 1) = W (k).
– until mk+1 additional data points are labeled, draw sample x from D∗ if |ŵk · x| ≥ bk , then reject x,∗ else, ask for label of x, and put into W (k + 1).

Theorem 5 Assume D is isotropic log-concave in Rd . There exist constants C1 , C2 s.t. for d ≥ 4,
, afterand for any ǫ, δ > 0, ǫ < 1/4, using Algorithm 1 with bk = C2k1 and mk = C2 d + ln 1+s−kδ1s = ⌈log2 cǫ ⌉ iterations, we find a separator of error at most ǫ with probability 1 − δ. The total
number of labeled examples needed is O((d + log(1/δ) + log log(1/ǫ)) log(1/ǫ)).
Proof Let c be the constantfrom Lemma 3. We will show, using induction, that, for all k ≤ s, withδ P
1probability at least 1 − 2 i<k (1+s−i)
2 , any ŵ consistent with the data in the working set W (k)has err(ŵ) ≤ c2−k , so that, in particular, err(wˆk ) ≤ c2−k .
The case where k = 1 follows from the standard VC bounds (see e.g.,(Vapnik and Chervonenkis,
1971)). Assume now the claim is true for k − 1 (k > 1), and consider the kth iteration. Let
S1 = {x : |ŵk−1 · x| ≤ bk−1 }, and S2 = {x P
: |ŵk−1 · x| > bk−1 }. By the induction hypothesis,1
we know that, with probability at least 1 − 2δ i<k−1 (1+s−i)
2 , all ŵ consistent with W (k − 1),
including ŵk−1 , have errors at most c2−(k−1) . Consider an arbitrary such ŵ. By Lemma 3 wehave θ(ŵ, w∗ ) ≤ 2−(k−1) and θ(ŵk−1 , w∗ ) ≤ 2−(k−1) , so θ(ŵk−1 , ŵ) ≤ 4 × 2−k . Applying Theorem 4, there is a choice of C1 (the constant such that bk−1 = C1 /2k−1 ) that satisfies−k−kP((ŵk−1 · x)(ŵ · x) < 0, x ∈ S2 ) ≤ c24 and P((ŵk−1 · x)(w∗ · x) < 0, x ∈ S2 ) ≤ c24 . So
c2−k
.
(6)
2
Now let us treat the case that x ∈ S1 . Since we are labeling mk data points in S1 at iterationk − 1, classic Vapnik-Chervonenkis bounds (1971) imply that, if C2 is a large enough absolute
constant, then with probability 1 − δ/(4(1 + s − k)2 ), for all ŵ consistent with the data in W (k),P((ŵ · x)(w∗ · x) < 0, x ∈ S2 ) ≤err(ŵ|S1 ) = P((ŵ · x)(w∗ · x) < 0 | x ∈ S1 ) ≤
8

c
c2−k
=
.
4bk
4C1

(7)

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

Finally, since S1 consists of those points that, after projecting onto the direction ŵk−1 , fall into
an interval of length 2bP
k , Lemma 2 implies that P(S1 ) ≤ 2bk . Putting this together with (6) and (7),δ1−k , completing the proof.
with probability 1 − 2 i<k (1+s−i)
2 , we have err(ŵ) ≤ c2

5. Passive Learning
In this section we show how an analysis that was inspired by active learning leads to optimal (up to
constant factors) bounds for polynomial-time algorithms for passive learning.
Theorem 6 Assume that D is zero mean and log-concave in Rd . There exists an absolute constantC3 s.t. for d ≥ 4, and for any ǫ, δ > 0, ǫ < 1/4, any algorithm that outputs a hypothesis thatexamples finds a separator of error at most ǫ with probability
correctly classifies m = C3 (d+log(1/δ))ǫ≥ 1 − δ.
P ROOF S KETCH : We focus here on the case that D is isotropic. We can treat the non-isotropic
case by observing that the two cases are equivalent; one may pass between them by applying thewhitening transform. (See Appendix C for details.)
While our analysis will ultimately provide a guarantee for any learning algorithm that always
outputs a consistent hypothesis, we will use intermediate hypothesis of Algorithm 1 in the analysis.
Let c be the constant from Lemma 3. While proving
 Theorem 5, we proved that, if Algorithm 1
C1
1+s−k
is run with bk = 2k and mk = C2 d + ln δ, that for all k ≤ s, with probability ≥ 1 −δ P
1−ki<k (1+s−i)2 any ŵ consistent with the data in W (k) has err(ŵ) ≤ c2 . Thus, after s =2O(log(1/ǫ)) iterations, with probability at least ≥ 1 − δ, any linear classifier consistent with all thetraining data has error ≤ ǫ, since any such classifier is consistent with the examples in W (s).
Now, let us analyze the number of examples used, including those examples whose labels were
not requested by Algorithm 1. Lemma 2 implies that there is a positive constant c1 such that
P(S1 ) ≥ c1 bk : again, S1 consists of those points that fall into an interval of length 2bk after projecting onto ŵk−1 . The density is lower bounded by a constant when bk ≤ 1/9, and we can use
the bound for 1/9 when bk > 1/9. The expected number of examples that we need before we findkk
. Using a Chernoff bound, if we draw 2m
mk elements of S1 is therefore at most cm
c1 bk examples,
1 bk
the probability that we fail to get mk members of S1 is at most exp (−mk /6), which
P is atk mostδ/(4(1 + s − k)2 ) if C2 is large enough. So, the total number of examples needed, k 2m
c1 bk , is at
most a constant factor more than



s
s
X
X
1+s−k
k
2k log(1 + s − k)= O(2s (d + log(1/δ))) +2 d + log
δ
k=1
k=1
 X

s
d + log(1/δ)
2k log(1 + s − k).
+
=O
ǫ
k=1

P
We can show sk=1 2k log(1 + s − k) = O(1/ǫ), completing the proof.
We conclude this section by pointing out several important facts and implications of Theorem 6
and its proof.
(1) The separator in Theorem 6 (and the one in Theorem 5 ) can be found in polynomial time, forexample by using linear programming.
9

BALCAN L ONG(2) The analysis of Theorem 6 also bounds the number of unlabeled examples needed by theactive learning algorithm of Theorem 5. This shows that an algorithm can request a nearly
optimally small number of labels without increasing the total number of examples requiredby more than a constant factor. Specifically, in round k, we only need 2k (d + ln[(1 + s −k)/δ]) unlabeled examples (whp), where s = O(log(1/ǫ)), so the total number of unlabeled
examples needed over all rounds is O(d/ǫ + log(1/δ)/ǫ).

6. More Distributions
In this section we consider learning with respect to a more general class of distributions. We startby providing a general set of conditions on a set D of distributions that is sufficient for efficientpassive and active learning w.r.t. distributions in D. We now consider nearly log-concave distributions, an interesting, more general class containing log-concave distributions, considered previouslyin (Applegate and Kannan, 1991) and (Caramanis and Mannor, 2007). We then prove that isotropic
nearly log-concave distributions satisfy our sufficient conditions; in Appendix D, we also show how
to remove the assumption that the distribution is isotropic.
Definition 7 A set D of distributions is admissible if it satisfies the following:• There exists c such that for any D ∈ D and any two unit vectors u and v in Rd we havecθ(v, u) ≤ dD (u, v).
• For any c1 > 0, there is a c2 > 0 such that the following holds for all D ∈ D. Let u and v be
two unit vectors in Rd s.t. θ(u, v) = α < π/2. Then Px∼D [sign(u · x) 6= sign(v · x), |v · x| ≥c2 α] ≤ c1 α.
• There are positive constants c3 , c4 , c5 such that, for any D ′ ∈ D, for any projection D of D ′ onto
a one-dimensional subspace, the density f of D satisfies f (x) < c3 for all x and f (x) > c4
for all x with |x| < c5 .
The proofs of Theorem 5 and Theorem 6 can be used without modification to show:
Theorem 8 If D is admissible, then arbitrary f ∈ C can be learned with respect to arbitrary distributions in D in polynomial time in the active learning model fromlog(1/ǫ)) log(1/ǫ)) O((d+log(1/δ)+log
d+log(1/δ)
examples.
labeled examples, and in the passive learning model from Oǫ6.1. The nearly log-concave caseDefinition 9 A density function f : Rn → R is β log-concave if for any λ ∈ [0, 1], x1 ∈ Rn ,x2 ∈ Rn , we have f (λx1 + (1 − λ)x2 ) ≥ e−β f (x1 )λ f (x2 )1−λ .
Clearly, a density function f is log-concave if it is 0-log-concave. An example of a O(1)-logconcave distribution is a mixture of two log-concave distributions whose covariance matrices are I,
and whose means µ1 and µ2 have ||µ1 − µ2 || = O(1).
In this section we prove that for any sufficiently small constant β ≥ 0, the class of isotropic
β log-concave distribution in Rd is admissible and has light tails (this second fact is useful for
analyzing the disagreement coefficient in Sections 8). In doing so we provide several new properties
for such distributions, which could be of independent interest. Detailed proofs of our claims appear
in Appendix D.
We start by showing that for any isotropic√ β log-concave density f there exists a log-concave
density f˜ whose center is within e(C − 1) Cd of f ’s center and that satisfies f (x)/C ≤ f˜(x) ≤10

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

Cf (x), for C as small as eβ log d . The fact C depends only exponentially in log d (as opposed toexponentially in d) is key for being able to argue that such distributions have light tails.
Lemma 10 For any isotropic β log-concave density function f there exists a log-concave density√Rfunction f˜ that satisfies f (x)/C ≤ f˜(x) ≤ Cf (x) andx(f (x) − f˜(x))dx ≤ e(C − 1) Cd,
R
for C = eβ⌈log2 (d+1)⌉ . Moreover, we have 1/C ≤ (u · x)2 f˜(x)dx ≤ C for every unit vector u.

P ROOF S KETCH : Note that if the density function f is β log-concave we have that h = ln fsatisfies that for any λ ∈ [0, 1], x1 ∈ Rn , x2 ∈ Rn , we have h(λx1 + (1 − λ)x2 ) ≥ −β + λh(x1 ) +(1−λ)h(x2 ). Let ĥ be the function whose subgraph is the convex hull of the subgraph of h. By using
P
Caratheodory’s theorem2 we can show that ĥ(x) = maxPd+1 αi =1,αi ≥0,x=Pd+1 αi xi d+1
i=1 αi h(xi ).
i=1

i=1

This implies h(x) ≤ ĥ(x) and we can prove by induction on log2 (d + 1) that h(x) ≥ ĥ(x) −β⌈log2 (d + 1)⌉. If we further normalize eĥ to make it a density function, we obtain f˜ that is logconcave and satisfies f (x)/C ≤ f˜(x) ≤ Cf (x), where C = eβ⌈log2 (d+1)⌉ . This implies that forany x we have |f (x) − f˜(x)| ≤ (C − 1)f˜(x).
Using this fact and concentration properties of f˜ (in particular Lemma 2), we can show that thecenter of f˜ is close to the center of f , as desired.
Theorem 11 Assume β is a sufficiently small non-negative constant and let D be the set of all
isotropic β log-concave
distributions. (a) D is admissible. (b) Any D ∈ D has light tails. That is:√P(||X|| > R Cd) < Ce−R+1 , for C = eβ⌈log2 (d+1)⌉ .

P ROOF S KETCH : (a) Choose D ∈ D. As in Lemma 3, consider the plane determined by u andv and let proju,v (x) denote the projection operator that given x ∈ Rd , orthogonally projects x onto
this plane. If D2 = proju,v (D) then dD (u, v) = dD2 (u′ , v ′ ). By using the Prekopa-Leindler inequality (Gardner, 2002) one can show that D2 is β log-concave (see e.g., (Caramanis and Mannor,
2007)). Moreover, if D is isotropic, than D2 is isotropic as well. By Lemma 10 we know that
there exists a C-isotropic log-concave
distribution D̃2 centered at z, kzk ≤ ǫ, satisfying f (x)/C ≤R
2 f (x)dx ≤ C for every unit vector u, for constants C = eβf˜(x) ≤ Cf (x) and
1/C
≤
(u
·
x)
p
√
and ǫ = e(C −1) 2C. For β sufficiently small we have (1/20+ǫ)/ 1/C − ǫ2 ≤ 1/9. Using this,by applying the whitening transform (see Theorem 16 in Appendix D), we can show f˜2 (x) ≥ c, for
kxk ≤ 1/20 , which implies f2 (x) ≥ c/C, for kxk ≤ 1/20. Using a reasoning as in Lemma 3
we get cθ(v, u) ≤ dD (u, v). The generalization of Theorem 4 follows from a similar proof, except
using Theorem 16. The density bounds in the n = 1 case also follow from Theorem 16 as well.
(b) Since X is isotropic, we have Ef [X · X] = d (where f is its associated density). By
Lemma 10, there exists a log-concave density f˜ such that f (x)/C ≤ f˜(x) ≤ Cf (x), for C =eβ⌈log2 (d+1)⌉ . This implies Ef˜[X · X] ≤ Cd. By Lemma 2 we get that that under f˜, P(||X|| >√√R Cd) < e−R+1 , so under f we have P(||X|| > R Cd) < Ce−R+1 .
Using Theorem 8 and Theorem 11(a) we obtain:
Theorem 12 Let β ≥ 0 be a sufficiently small constant. Assume that D is an isotropic β logconcave distribution in Rd . Then arbitrary f ∈ C can be learned with respect to D in polynomial
time in the active learning model from O((d+ log log(1/ǫ)) log(1/ǫ)) labeled examples, log(1/δ)+
d+log(1/δ)
examples.
and in the passive learning model from Oǫ
2. Caratheodory’s theorem states that if a point x of Rd lies in the convex hull of a set P , then there is a subset P̂ of P
consisting of d + 1 or fewer points such that x lies in the convex hull of P̂ .

11

BALCAN L ONG

7. Lower Bounds
In this section we give lower bounds on the label complexity of passive and active learning of
homogeneous linear separators when the underlying distribution is β log-concave, for a sufficiently
small constant β. These lower bounds are information theoretic, applying to any procedure, thatmight not be necessarily computationally efficient. The proof is in Appendix E.
Theorem 13 For a small enough constant β we have: (1) for any β log-concave distribution D
whose covariance matrix has full rank, the sample complexity of learning
origin-centered linear
separators under D in the passive learning model is Ω dǫ + 1ǫ log 1δ ; (2) the samplecomplexityof active learning of linear separators under β log-concave distributions is Ω d log 1ǫ .

Note that, if the covariance matrix of D does not have full rank, the number of dimensions iseffectively less than d, so our lower bound essentially applies for all log-concave distributions.

8. The inseparable case: Disagreement-based active learning
We consider two closely related distribution dependent capacity notions: the Alexander capacity
and the disagreement coefficient; they have been widely used for analyzing the label complexityof non-aggressive active learning algorithms (Hanneke, 2007; Dasgupta et al., 2007; Koltchinskii,
2010; Hanneke, 2011; Beygelzimer et al., 2010). We begin with the definitions. For r > 0, define
B(w, r) = {u ∈ C : PD (sign(u · x) 6= sign(w · x)) ≤ r}. For any H ⊆ C, define the regionof disagreement as DIS(H) = {x ∈ X : ∃w, u ∈ H s.t. sign(u · x) 6= sign(w · x))}. Define the∗ ,r)))
Alexander capacity function capw∗ ,D (·) for w∗ ∈ C w.r.t. D as: capw∗ ,D (r) = PD (DIS(B(w.
rDefine the disagreement coefficients for w∗ ∈ C w.r.t. D as: disw∗ ,D (ǫ) = sup[capw∗ ,D (r)].
r≥ǫ

The following is our bound in the disagreement coefficient. Its proof is in Appendix F.
Theorem 14 Let β ≥ 0 be a sufficiently small constant. Assume that D is an isotropic β logβconcave distribution in Rd . For any w∗ , for any ǫ, capw∗ ,D (ǫ) is O(d1/2+ 2 ln 2 log(1/ǫ)). Thusβdisw∗ ,D (ǫ) = O(d1/2+ 2 ln 2 log(1/ǫ)).
Theorem 14 immediately leads to concrete bounds on the label complexity of several algorithms in the literature (Hanneke, 2007; Cohn et al., 1994; Balcan et al., 2006; Koltchinskii, 2010;
Dasgupta et al., 2007). For example, by composing it with a result of (Dasgupta et al., 2007), we
obtain a bound of Õ(d3/2 (log2 (1/ǫ) + (ν/ǫ)2 )) for agnostic active learning when D is isotropic
log-concave in Rd ; that is we only need Õ(d3/2 (log2 (1/ǫ) + (ν/ǫ)2 ))) label requests to output aclassifier of error at most ν + ǫ, where ν = minw∈C err(w).

9. The Tsybakov condition
In this section we consider a variant of the Tsybakov noise condition (Mammen and Tsybakov,
1999). We assume that the classifier h that minimizes P(x,y)∼DXY (h(x) 6= y) is a linear classifier,and that, for the weight vector w∗ of the optimal classifier, there exist known parameters α, a > 0such that, for all w, we havea(dD (w, w∗ ))1/(1−α) ≤ err(w) − err(w∗ ).
By generalizing Theorem 4 so that it provides a stronger bound for larger margins, and combining
the result with the other lemmas of this paper and techniques from (Balcan et al., 2007), we get thefollowing.
12

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

Theorem 15 Let s = O(log(1/ǫ)). Assume that the distribution DXY satisfies the Tsybakov noise
condition for constants α ∈ [0, 1) and a ≥ 0, and that the marginal D on R d is isotropic logconcave. (1) If α = 0, we can find a separator with excess error ≤ ǫ with probability1 − δ usingO(log(1/ǫ))(d + log(s/δ)) labeled examples in the active learning model, and O d+log(1/δ)ǫ
labeled examples in the passive learning model. (2) If α > 0, we can find a separator with excess
error ≤ ǫ with probability 1 − δ using O((1/ǫ)2α log2 (1/ǫ))(d + log(s/δ)) labeled examples in theactive learning model.
In the case α = 0 (that is more general than the Massart noise condition) our analysis leads tooptimal bounds for active and passive learning of linear separators under log-concave distributions, improving the dependence on d over previous best known results (Hanneke and Yang, 2012;
Giné and Koltchinskii, 2006). Our analysis for Tsybakov noise (α ≥ 0) leads to bounds on active
learning with improved dependence on d over previous known results (Hanneke and Yang, 2012) inthis case as well. Proofs and further details appear in Appendix G.

10. Discussion and Open Questions
The label sample complexity of our active learning algorithm for learning homogeneous linear separators under isotropic logconcave distributions
is O((d+ log(1/δ)+ log log(1/ǫ)) log(1/ǫ)), while
our lower bound for this setting is Ω d log 1ǫ . Our upper bound is achieved by an algorithm thatuses a polynomial number of unlabeled training examples, and polynomial time. If an unboundedamount of computation time and an unbounded number of unlabeled examples are available, it
seems to be easy to learn to accuracy ǫ using O(d log(1/ǫ)) label requests, no matter what the valueof δ. (Roughly, the algorithm can construct an ǫ-cover to initialize a set of candidate hypotheses,
then repeatedly wait for an unlabeled example that evenly splits the current list of candidates, andask its label, eliminated roughly half of the candidates.) It would be interesting to know what is thebest label complexity for a polynomial-time algorithm, or even an algorithm that is constrained touse a polynomial number of unlabeled examples.
Conceptually, our analysis of ERM for passive learning under (nearly) log-concave distributions
is based on a more aggressive localization than those considered previously in the literature. It would
be very interesting to extend this analysis as well as our analysis for active learning to arbitrary
distributions and more general concept spaces.
Acknowledgements We thank Steve Hanneke for a number of useful discussions.
This work was supported in part by NSF grant CCF-0953192, AFOSR grant FA9550-09-1-0538,
and a Microsoft Research Faculty Fellowship.

References
K.S. Alexander. Rates of growth and sample moduli for weighted empirical processes indexed bysets. Probability Theory and Related Fields, 1987.
N. Alon. A non-linear lower bound for planar epsilon-nets. FOCS, pages 341–346, 2010.
D. Applegate and R. Kannan. Sampling and integration of near log-concave functions. In STOC,
1991.
P. Assouad. Plongements lipschitziens dans. R . Bull. Soc. Math. France, 111(4):429–448, 1983.
13

BALCAN L ONG

M. F. Balcan, A. Beygelzimer, and J. Langford. Agnostic active learning. In ICML, 2006.
M.-F. Balcan, A. Broder, and T. Zhang. Margin based active learning. In COLT, 2007.
M.-F. Balcan, S. Hanneke, and J. Wortman. The true sample complexity of active learning. In
COLT, 2008.
P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics,
2005.
A. Beygelzimer, D. Hsu, J. Langford, and T. Zhang. Agnostic active learning without constraints.
In NIPS, 2010.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the VapnikChervonenkis dimension. JACM, 36(4):929–965, 1989.
S. Boucheron, O. Bousquet, and G. Lugosi. Theory of classification: a survey of recent advances.
ESAIM: Probability and Statistics, 2005.
N. H. Bshouty, Y. Li, and P. M. Long. Using the doubling dimension to analyze the generalizationof learning algorithms. JCSS, 2009.
C. Caramanis and S. Mannor. An inequality for nearly log-concave distributions with applications
to learning. IEEE Transactions on Information Theory, 2007.
R. Castro and R. Nowak. Minimax bounds for active learning. In COLT, 2007.
N. Cesa-Bianchi, C. Gentile, and L. Zaniboni. Learning noisy linear classifiers via adaptive andselective sampling. Machine Learning, 2010.
K. L. Clarkson and K. Varadarajan. Improved approximation algorithms for geometric set cover.
Discrete Comput. Geom., 37(1):43–58, 2007.
D. Cohn, L. Atlas, and R. Ladner. Improving generalization with active learning. In ICML, 1994.
S. Dasgupta. Coarse sample complexity bounds for active learning. In NIPS, volume 18, 2005.
S. Dasgupta. Active learning. Encyclopedia of Machine Learning, 2011.
S. Dasgupta, A. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning. In COLT,
2005.
S. Dasgupta, D.J. Hsu, and C. Monteleoni. A general agnostic active learning algorithm. Advancesin Neural Information Processing Systems, 20, 2007.
O. Dekel, C. Gentile, and K. Sridharan. Selective sampling and active learning from single andmultiple teachers. Journal of Machine Learning Research, 2012.
A. Ehrenfeucht, D. Haussler, M. Kearns, and L. G. Valiant. A general lower bound on the numberof examples needed for learning. Information and Computation, 1989.
Y. Freund, H.S. Seung, E. Shamir, and N. Tishby. Selective sampling using the query by committee
algorithm. Machine Learning, 28(2-3):133–168, 1997.
14

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

E. J. Friedman. Active learning for smooth problems. In COLT, 2009.
R. J. Gardner. The Brunn-Minkowski inequality. Bull. Amer. Math. Soc., 2002.
E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for ratio type empirical processes. The Annals of Probability, 34(3):1143–1216, 2006.
A. Gonen, S. Sabato, and S. Shalev-Shwartz. Efficient pool-based active learning of halfspaces. In
ICML, 2013.
S. Hanneke. A bound on the label complexity of agnostic active learning. In ICML, 2007.
S. Hanneke. Rates of convergence in active learning. The Annals of Statistics, 39(1):333–361, 2011.
S. Hanneke and L. Yang.
http://arxiv.org/abs/1207.3772.

Surrogate losses in passive and active learning, 2012.

D. Haussler, N. Littlestone, and M. K. Warmuth. Predicting {0, 1}-functions on randomly drawn
points. Information and Computation, 115(2):129–161, 1994.
David Haussler and Emo Welzl. Epsilon nets and simplex range queries. Disc. Comp. Geometry, 2:
127–151, 1987.
A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically learning halfspaces. In Proceedings of the 46th Annual Symposium on the Foundations of Computer Science (FOCS), 2005.
M. Kearns and U. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.
A. R. Klivans, P. M. Long, and R. A. Servedio. Learning halfspaces with malicious noise. JMLR,
2009a.
A. R. Klivans, P. M. Long, and A. Tang. Baum’s algorithm learns intersections of halfspaces withrespect to log-concave distributions. In RANDOM, 2009b.
V. Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. Journalof Machine Learning Research, 11:2457–2485, 2010.
J. Komlós, J. Pach, and G. Woeginger. Almost tight bounds on epsilon-nets. Discrete and Computational Geometry, 7:163–173, 1992.
S. R. Kulkarni, S. K. Mitter, and J. N. Tsitsiklis. Active learning using arbitrary binary valued
queries. Machine Learning, 1993.
P. M. Long. On the sample complexity of PAC learning halfspaces against the uniform distribution.
IEEE Transactions on Neural Networks, 6(6):1556–1559, 1995.
P. M. Long. An upper bound on the sample complexity of PAC learning halfspaces with respect tothe uniform distribution. Information Processing Letters, 2003.
L. Lovasz and S. Vempala. The geometry of logconcave functions and sampling algorithms. Random Structures and Algorithms, 2007.

15

BALCAN L ONG

E. Mammen and A.B. Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27:
1808–1829, 1999.
P. Massart and E. Nedelec. Risk bounds for statistical learning. The Annals of Statistics, 2006.
S. Mendelson. Estimating the performance of kernel classes. Journal of Machine Learning Research, 4:759–771, 2003.
R. Nowak. The Geometry of Generalized Binary Search. IEEE Transactions on Information Theory,
2011.
J. Pach and P.K. Agarwal. Combinatorial Geometry. John Wiley and Sons, 1995.
M. Raginsky and A. Rakhlin. Lower bounds for passive and active learning. In NIPS, 2011.
L.G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
S. van de Geer. Empirical processes in M-estimation. Cambridge Series in Statistical and Probabilistic Methods, 2000.
A. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes With Applications
to Statistics. Springer, 1996.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events totheir probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971.
V. N. Vapnik. Estimation of Dependencies based on Empirical Data. Springer Verlag, 1982.
V. N. Vapnik. Statistical Learning Theory. John Wiley and Sons, 1998.
S. Vempala. A random-sampling-based algorithm for learning intersections of halfspaces. JACM,
57(6), 2010.

Appendix A. Additional Related Work
Learning with noise. Alexander Capacity and the Disagreement Coefficient Roughly speaking the Alexander capacity (Alexander., 1987; Giné and Koltchinskii, 2006) quantifies how fast theregion of disagreement of the set of classifiers at distance r of the optimal classifier collapses as afunction r; 3 the disagreement coefficient (Hanneke, 2007) additionally involves the supremum ofr over a range of values. (Friedman, 2009) provides guarantees on these quantities (for sufficiently
small r) for general classes of functions in Rd if the underlying data distribution is sufficiently
smooth. Our analysis implies much tighter bounds for linear separators under log-concave distributions (matching what was known for the much less general case of nearly uniform distribution overthe unit sphere); furthermore, we also analyze the nearly log-concave case where we allow an arbitrary number of discontinuities, a case not captured by the (Friedman, 2009) conditions at all. This
immediately implies concrete bounds on the labeled data complexity of several algorithms in theliterature including the A2 algorithm (Balcan et al., 2006) and the DHM algorithm (Dasgupta et al.,3. The region of disagreement DIS(C) of a set of classifiers C is the of set of instances x s.t. for each x ∈ DIS(C)there exist two classifiers f, g ∈ C that disagree about the label of x.

16

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

2007), with implications for the purely agnostic case (i.e., arbitrary forms of noise), as well as theKoltchinskii’s algorithm (Koltchinskii, 2010) and the CAL algorithm (Balcan et al., 2006; Hanneke,
2007, 2011). Furthermore, in the realizable case and under Tsybakov noise, we show even betterbounds, by considering aggressive active learning algorithms.
Note that as opposed to the realizable case, all existing active learning algorithms analyzed
under Massart and Tsybakov noise conditions using the learning model analyzed in this paper (including our algorithms in Theorem 15), as well as those for the agnostic setting, are not known to
run in time poly(d, 1/ǫ). In fact, even ignoring the optimality of sample complexity, there are no
known algorithms for passive learning that run in time poly(d, 1/ǫ) for general values of ǫ, evenfor the Massart noise condition and under log-concave distributions. Existing works on agnostic
passive learning under log-concave distributions either provide running times dpoly(1/ǫ) (e.g., thework of (Kalai et al., 2005)) or can only achieve values of ǫ that are significantly larger than thenoise rate (Klivans et al., 2009a).
Other Work on Active Learning Several papers (Cesa-Bianchi et al., 2010; Dekel et al., 2012)
present efficient online learning algorithms in the selective sampling framework, where labels mustbe actively queried before they are revealed. Under the assumption that the label conditional distribution is linear function determined by a fixed target vector, they provide bounds on the regret of thealgorithm and on the number of labels it queries when faced with an adaptive adversarial strategy
of generating the instances. As pointed by (Dekel et al., 2012), these results can be converted toa statistical setting when the instances xt are drawn i.i.d and they further assume a margin condition. In this setting they obtain exponential improvement in label complexity over passive learning.
While very interesting, these results are incomparable to ours; their techniques significantly exploit
the linear noise condition to get these improvements – note that such an improvement would not be
possible in the realizable case (as pointed for example in (Gonen et al., 2013)).
(Nowak, 2011) considers an interesting abstract “generalized binary search” problem with applications to active learning; while these results apply for more general concept spaces, it is notclear how to implement the resulting procedures in polynomial time and by using access to only apolynomial number of unlabeled samples from the underlying distribution (as required by the active
learning model). Another interesting recent work is that of (Gonen et al., 2013), which study active
learning of linear separators via an aggressive algorithm using a margin condition, using a generalapproximation guarantee on the number of labels requested; note that while these results work forpotentially more general distributions, as opposed to ours, they do not come with explicit (tight)
bounds on the label complexity.
ǫ-nets, Learning, and Geometry Small ǫ-nets are useful for many applications, especially in
Computational Geometry (see (Pach and Agarwal, 1995)). The same fundamental techniques of(Vapnik and Chervonenkis, 1971; Vapnik, 1982) have been applied to establish the existence ofsmall ǫ-nets (Haussler and Welzl, 1987) and to bound the sample complexity of learning (Vapnik,
1982; Blumer et al., 1989), and a number of interesting upper and lower bounds on the smallest
possible size of ǫ-nets have been obtained (Komlós et al., 1992; Clarkson and Varadarajan, 2007;
Alon, 2010).
Our analysis implies a O(d/ǫ) upper bound on the size of an ǫ-net for a set of regions of disagreement between all possible linear classifiers and the target, when the distribution is zero-mean
and log-concave. In particular, since in Theorem 6 we prove that any hypothesis consistent withthe training data has error rate ≤ ǫ with probability 1 − δ, setting δ to a constant gives a proof of aO(d/ǫ) bound on the size of an ǫ-net for the following set: {{x : (w · x)(w∗ · x) < 0} : w ∈ R n }.

17

BALCAN L ONG

Appendix B. Proof of Lemma 3
Lemma 3. Assume D is an isotropic log-concave in Rd . Then there exists c such that for any twounit vectors u and v in Rd we have cθ(v, u) ≤ dD (u, v).

Proof Consider two unit vectors u and v. Let proju,v (x) denote the projection operator that, givenx ∈ Rd , orthogonally projects x onto the plane determined by u and v. That is, if we define anorthogonal coordinate system in which coordinates 1, 2 lie in this plane and coordinates 3, . . . , d
are orthogonal to this plane, then x′ = proju,v (x1 , . . . , xd ) = (x1 , x2 ). Also, given distribution D
over Rd , define proju,v (D) to be the distribution given by first picking x ∼ D and then outputting
x′ = proju,v (x). That is, proju,v (D) is just the marginal distribution over coordinates 1, 2 in theabove coordinate system. Notice that if x′ = proju,v (x) then u · x = u′ · x′ where u′ = proju,v (u)and v ′ = proju,v (v). So, if D2 = proju,v (D) then dD (u, v) = dD2 (u′ , v ′ ).
By Lemma 2(c), we have that if D is isotropic and log-concave, then D2 is as well. Let A
to be the region of disagreement between u′ and v ′ intersected with the ball of radius 1/9 in R2 .
The probability mass of A under D2 is at least the volume of A times inf x∈A D2 (x). So, using
Lemma 2(b)dD2 (u′ , v ′ ) ≥ vol(A) inf D2 (x) ≥ cθ(u, v),x∈A

as desired.

Appendix C. Passive Learning
Theorem 6. Assume that D is zero mean and log-concave in Rd . There exists an absolute constantC3 s.t. for d ≥ 4, and for any ǫ, δ > 0, ǫ < 1/4, any algorithm that outputs a hypothesis thatexamples finds a separator of error at most ǫ with probability
correctly classifies m = C3 (d+log(1/δ))ǫ≥ 1 − δ.

Proof First, let us prove the theorem in the case that D is isotropic. We will then treat the generalcase at the end of the proof.
While our analysis will ultimately provide a guarantee for any learning algorithm that always
outputs a consistent hypothesis, we will use intermediate hypothesis of Algorithm 1 in the analysis.
Let c be the constant from Lemma 3. While proving
 Theorem 5, we proved that, if Algorithm 1
C1
1+s−k
is run with bk = 2k and mk = C2 d + ln δ, that for all k ≤ s, with probability ≥ 1 −
δ P
1
any
ŵ
consistent
with
the
data
in
W
(k) has err(ŵ) ≤ c2−k . Thus, after s =i<k (1+s−i)22O(log(1/ǫ)) iterations, with probability at least ≥ 1 − δ, any linear classifier consistent with all thetraining data has error ≤ ǫ, since any such classifier is consistent with the examples in W (s).
Now, let us analyze the number of examples used, including those examples whose labels were
not requested by Algorithm 1. Lemma 2 implies that there is a positive constant c1 such that
P(S1 ) ≥ c1 bk : again, S1 consists of those points that fall into an interval of length 2bk after projecting onto ŵk−1 . The density is lower bounded by a constant when bk ≤ 1/9, and we can use thebound for 1/9 when bk > 1/9.
The expected number of examples that we need before we find mk elements of S1 is thereforekk. Using a Chernoff bound, if we draw 2m
at most cm
c1 bk examples, the probability that we fail to
1 bk

18

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

get mk members of S1 is at most exp (−mk /6), which
is at most δ/(4(1 + s − k)2 ) if C2 is large
P 2menough. So, the total number of examples needed, k c1 bkk , is at most a constant factor more than
s
X

k

2

k=1



d + log



1+s−k
δ

= O(2s (d + log(1/δ))) +=O

We claim thatPsd + log(1/δ)
ǫ



+



s
X

k=1
s
X
k=1

2k log(1 + s − k)

2k log(1 + s − k).

k
k=1 2 log(1 + s − k) = O(1/ǫ). We havesX
k=1

2k log(1 + s − k) ≤

s
X
k=1

2k (3 + s − k)

≤

Z s+1

=

2(2s − 1)(1 + ln(4)) − s ln 2

k=1

2k (3 + s − k)(since 2k (3 + s − k) is increasing for k ≤ s + 1)
ln2 2

= O(1/ǫ),completing the proof in the case that D is isotropic.
Now let us treat the case in which D is not isotropic. Suppose that Σ is the covariance matrix, an algorithm isof D, so that Σ−1/2 is the “whitening transform”. Suppose, for m = C3 (d+log(1/δ))ǫ
given a sample S of examples (x1 , y1 ), ..., (xm , ym ) for x1 , ..., xm drawn according to D, and ymlabeled by a target hypothesis with weight vector v. Note that w is consistent with S if and only
if wT Σ1/2 is consistent with (Σ−1/2 x1 , y1 ), ..., (Σ−1/2 xm , ym ) (so those examples are consistent
with v T Σ1/2 ). So our analysis of the isotropic case implies that, with probability 1 − δ, for any w
consistent with (x1 , y1 ), ..., (xm , ym ), we haveP(sign((wT Σ1/2 )(Σ−1/2 x)) 6= sign((v T Σ1/2 )(Σ−1/2 x))) ≤ ǫ,
which of course means that P(sign(wT x) 6= sign(v T x)) ≤ ǫ.

Appendix D. More Distributions
D.1. Isotropic Nearly Log-concave distributions
Lemma 10. For any isotropic β log-concave density function f there exists a log-concave density√Rfunction f˜ that satisfies f (x)/C ≤ f˜(x) ≤ Cf (x) andx(f (x) − f˜(x))dx ≤ e(C − 1) Cd,
R
for C = eβ⌈log2 (d+1)⌉ . Moreover, we have 1/C ≤ (u · x)2 f˜(x)dx ≤ C for every unit vector u.
Proof Note that if the density function f is β log-concave we have that h = ln f satisfies that forany λ ∈ [0, 1], x1 ∈ Rn , x2 ∈ Rn , we have h(λx1 + (1 − λ)x2 ) ≥ −β + λh(x1 ) + (1 − λ)h(x2 ).
19

BALCAN L ONG

Let ĥ be the function whose subgraph is the convex hull of the subgraph of h. That is, ĥ(x) isPthe maximum of all values of ki=1 αi h(ui ) for any u1 , ..., uk ∈ R d and α1 , ..., αk ∈ [0, 1] suchP
P
that ki=1 αi = 1 and x = ki=1 αi ui . Note that, if the components of ui are ui,1 , ..., u1,d , we canget ĥ(x) by starting with
T = {(u1,1 , ..., u1,d , h(u1 )), ..., (uk,1 , ..., uk,d , h(uk ))}taking the convex combination of the members of T with mixing coefficients α1 , ..., αk , and thenreading off the last component. Caratheodory’s theorem4 implies that we can get the same result
using a mixture of at most d + 1 members of T . In other words, we can assume without loss ofgenerality that k = d + 1, so thatĥ(x) = P

max

d+1
X

Pd+1
d+1
i=1 αi =1,αi ≥0,x= i=1 αi xi i=1

αi h(xi ).

(8)

Because of the case where (α1 , ..., αd+1 ) concentrates all its weight on one component, we haveh(x) ≤ ĥ(x).
We also claim thath(x) ≥ ĥ(x) − β⌈log2 (d + 1)⌉.
(9)
We will prove this by induction on log2 (d + 1), treating the case in which d + 1 is a power of 2. (Bypadding with zeroes if necessary, we may assume without loss of generality that d + 1 is a powerof 2.) The base case, in which d = 1, follows
P immediately from the definitions. Let k = d + 1.
Assume that x = a1 x1 + a2 x2 + ... + ak xk , ki=1 ai = 1, ai ≥ 0. We can write this as:
x = (a1 + a2 )x1,2 + (a3 + a4 )x3,4 + ...(ak−1 + ak )xk−1,kai
i+1where xi,i+1 = ai +a
xi + aia+axi+1 , for all i. Now, by induction we have:
i+1
i+1

h(x) ≥ −β log(k/2) + (a1 + a2 )h(x1,2 ) +... + (ak−1 + ak )h(xk−1,k )≥ −β log(k/2)− (a1 + a2 )β + a1 h(x1 ) + a2 h(x2 )− (a3 + a4 )β + a3 h(x3 ) + a4 h(x4 ) +...
− (ak−1 + ak )β + ak−1 h(xk−1 ) + ak h(xk )= −β log(k) + a1 h(x1 ) + a2 h(x2 ) + a3 h(x3 ) + ...ak h(xk ).
P
The last inequality follows from the fact that ni=1 ai = 1.
So, we have proved (9). If we further normalize eĥ to make it a density function, we obtain f˜that is log-concave and satisfies f (x)/C ≤ f˜(x) ≤ Cf (x), where C = eβ⌈log2 (d+1)⌉ . This implies
that for any x we have |f (x) − f˜(x)| ≤ (C − 1)f˜(x).
4. Caratheodory’s theorem states that if a point x of Rd lies in the convex hull of a set P , then there is a subset P̂ of P
consisting of d + 1 or fewer points such that x lies in the convex hull of P̂ .

20

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

We now show that the center of f˜ is close to the center of f . We have:ZZ˜x(f (x) − f (x))dx ≤kxk |f (x) − f˜(x)|dxZZ ∞Pf˜[kXk ≥ r]dr.
≤ (C − 1) kxk f˜(x)dx = (C − 1)
r=0

Using concentration properties of f˜ (in particular Lemma 2) we getZZ ∞− √r +1˜
x(f (x) − f (x))dx ≤ (C − 1)e Cd drr=0√= e(C − 1) Cd,
as desired.

Theorem 16 (i) Let f : R2 → R be the density function of a log-concave distribution centeredat z andRwith covariance matrix A = Ef [(X − z)(X − z)T ]. Assume f satisfies kzk ≤ ξ and1/C ≤ (u · x)2 f (x)dxp≤ C for every unit vector u, for C ≥ 1 constant close to 1. We have:(a) Assume (1/20 + ξ)/ 1/C − ξ 2 ≤ 1/9. Then there exist an universal constant c s.t. we havef (x) ≥ c, for all x with 0 ≤ ||x|| ≤ 1/20. (b) Assume C ≤ 1 + 1/5. There exist universal constants
c1 and c2 such that f (x) ≤ C1 exp(−C2 ||x||) for all x.
(ii) Let f : R → Rpbe the density function of a log-concave distribution centered at ξ withstandard deviation σ = Varf (X).
p Then f (x) ≤ 1/σ for all x. If furthermore f satisfies 1/C ≤Ef [X 2 ] ≤ C for C ≥ 1 and ξ/ 1/C − ξ 2 ≤ 1/9, then we have f (0) ≥ c for some universal
constant c.
Proof (i) Let Y = A−1/2 (X − z). Then Y is a log-concave distribution in the isotropic position.
Moreover, the density function of g is given by g(y) = det(A1/2 )f (A1/2 y +z). Let M = E[XX T ].
We have
A = E[(X − z)(X − z)T ] = E[XX T ] − zz T = M − zz T .
R
Also, the fact 1/C ≤ (u · x)2 f (x)dx ≤ C for every unit vector u is equivalent to
1/C ≤ uT E[XX T ]u ≤ C√√
for every unit vector u. Using v = (1, 0), v = (0, 1), and v = (1/ 2, 1/ 2) we get that M1,1 ∈[1/C, C], M2,2
p∈ [1/C, C], and M1,2 = M2,1 ∈ [1/C − C, C − 1/C]. We also have kzk ≤ ξ anddet(A1/2 ) = det(A). All these imply thatp
(1/C − ξ 2 )2 − (C − 1/C)2 ≤ det(A1/2 ) ≤ C.

(a) For x = A1/2 y+z we have kx −pzk2 = (x−z)(x−z)T = kyk2 v T Av, where v = (1/ kyk)yis a unit vector, so kyk ≤ kx − zk / 1/C − ξ 2 . If kxk ≤ 1/20 we have kyk ≤ 1/9, so by
Lemma 2 we have g(y) ≥ c1 , so f (y) ≥ c, for some universal constants c1 , c2 , as desired.
1−1/2 (x − z)). By Lemma 2 (b) we have(b) We have f (x) = det (A1/2 ) g(Af (x) ≤

i
h
1
−1/2
.
exp
−c
A
(x
−
z)
det A1/2
21

BALCAN L ONG

By the triangle inequality we further obtain:
h
i
h
i
1
−1/2
−1/2
exp
c
A
z
exp
−c
A
x
.
f (x) ≤det (A1/2)√
2
For C ≤ 1+1/5, we can show that A−1/2 x ≥ (1/ 2) kxk. It is enough to show A−1/2 x ≥(1/2) kxk2 , or that 2 kvk2 ≥ A1/2 v , where v = A−1/2 x (so x = A1/2 v). This is equivalent to
2v T v ≥ v T Av, which is true since the matrix 2I − A is positive semi-definite.
(ii) Define Y = (X − z)/σ. We have E[Y ] = 0 and E[Y 2 ] = 1. The density g of Y is given byg(y) = σf (σy + z). Now, since g is isotropic and log-concave, we can apply Lemma 2(e ) to g. So
g(y) ≤ 1 for all y. So, σf (σy + z) ≤ 1 for all y, which implies f (x) ≤ 1/σ for all x. The second
part follows as in Theorem 16.

D.2. More covariance matrices
In this section, we extend Theorem 5 to the case of arbitrary covariance matrices.
Theorem 17 If all distributions in D are zero-mean and log-concave in Rd , then arbitrary f ∈ C
be learned in polynomial time from arbitrary distributions in D in the active learning model fromO((d +log(1/δ) + log log(1/ǫ)) log(1/ǫ)) labeled examples, and in the passive learning modelfrom O d+log(1/δ)
examples.
ǫ
Our proof is through a series of lemma. First, (Lovasz and Vempala, 2007) have shown how to
reduce to the nearly isotropic case.
Lemma 18 ((Lovasz and Vempala, 2007)) For any constant κ > 0, there is a polynomial timealgorithm that, given polynomially many samples from a log-concave distribution D, outputs anestimate Σ of the covariance matrix of D such that, with probability 1 − δ the distribution D ′1≤ E((u · x)2 ) ≤ 1 + κ for all unit
obtained by sampling x from D and producing Σ−1/2 x has 1+κ
vectors u.
As a result of Lemma 18, we can assume without loss of generality that the distribution D
1≤ E((u · x)2 ) ≤ 1 + κ for an arbitrarily small constant κ. By Theorem 16, this implies
satisfies 1+κ
that, without loss of generality, there are constants c1 , ..., c4 such that, for the density f of any one
or two-dimensional marginal D ′ of D, we havef (x) ≥ c1 for all x with ||x|| ≤ c2 ,(10)f (x) ≤ c3 exp(−c4 ||x||).

(11)

and for all x,
We will show that these imply that D is admissible.

Lemma 19 (a) There exists c such that for any two unit vectors u and v in Rd we have cθ(v, u) ≤dD (u, v).
(b) For any c6 > 0, there is a c7 > 0 such that the following holds. Let u and v be two unit
vectors in Rd , and assume that θ(u, v) = α < π/2. Then
Px∼D [sign(u · x) 6= sign(v · x), |v · x| ≥ c7 α] ≤ c6 α.
22

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONSProof (a) Projecting D onto a subspace can only reduce the norm of its mean, and its variance in any
direction. Therefore, as in the proof of Lemma 3, we may assume without loss of generality that d =2. Here, let us define A to be the region of disagreement between u′ and v ′ intersected with the ballBc2 of radius c2 in R2 . Then we have dD2 (u′ , v ′ ) ≥ vol(A) inf x∈A D2 (x) ≥ vol(Bc2 )c1 θ(u, v).
(b) This proof basically amounts to observing that everything that was needed for the proof of
Theorem 4 is true for D, because of (10) and (11).
Armed with Lemma 19, to prove Theorem 17, we can just apply Theorem 8.

Appendix E. Lower Bounds
The proof of our lower bounds (Theorem 13) relies on a lower bound on the packing numbers
MD (C, ǫ). Recall that the ǫ-packing number, MD (C, ǫ), is the maximal cardinality of an ǫ-separated
set with classifiers from C, where we say that w1 , ..., wN are ǫ-separated w.r.t D if dD (wi , wj ) > ǫfor any i 6= j.
Lemma 20 There is a positive constant c such that, for all β < c, the following holds. Assume that
D is β log-concave in Rd , and√that its covariance matrix has full rank. For all sufficiently small ǫ,

c d−1
− 1.
d ∈ N , we have MD (C, ǫ) ≥ 2d 2ǫ

Proof We first prove the lemma in the case that D is isotropic. The proof in this case follows theoutline of a proof for the special case of the uniform distribution in (Long, 1995).
Let UBALLd be the uniform distribution on the surface of the unit ball in Rd . By Theorem 11,
there exists c such that for any two unit vectors u and v in Rd we have cθ(v, u) ≤ dD (u, v). Thisimplies that for a fixed u the probability that a randomly chosen v has dD (u, v) ≤ ǫ is upper boundedby the volume of those vectors in the interior of the unit ball whose angle is at most ǫ/c divided
by the volume of the unit ball. Using known bounds on this ratio (see (Long, 1995)) we have
d−1
d−1
, so Pu,v∈UBALLd [dD (u, v) ≤ ǫ] ≤ √1d 2ǫ
. ThatPv∈UBALLd [dD (u, v) ≤ ǫ] ≤ √1d 2ǫccmeans that for a fixed s if we pick s normal vectors at random from the unit ball, then the expectedd−12. Removing one
number of pairs of half-spaces that are ǫ-close according to D is at most √s 2ǫ
d c
d−1
2
s
2ǫ
element of each pair from S yields a set of s − √ chalfspaces that are ǫ-separated. Setting√ds = (2ǫ/c)dd−1 , leads the desired result.

To handle the non-isotropic case, suppose that Σ is the covariance matrix of D, so that Σ−1/2is the whitening transform. Let D ′ be the whitened version of D, i.e. the distribution obtained byfirst choosing x from D, and then producing Σ−1/2 x. We have dD (v, w) = dD′ (vΣ1/2 , wΣ1/2 )(because sign(v · x) 6= sign(w · x) iff sign((vΣ1/2 ) · (Σ−1/2 x)) 6= sign((wΣ1/2 ) · (Σ−1/2 x))). So
we can use an ǫ-packing w.r.t. D ′ to construct an ǫ-packing of the same size w.r.t. D.
Now we are ready to prove Theorem 13.
Theorem 13. For a small enough constant β we have: (1) for any β log-concave distribution D
whose covariance matrix has full rank, the sample complexity of learning
origin-centered linear
separators under D in the passive learning model is Ω dǫ + 1ǫ log 1δ ; (2) the sample complexity

of active learning of linear separators under β log-concave distributions is Ω d log 1ǫ .

Proof First, let us consider passive PAC learning. It is known (Long, 1995) that, for any distribution
D, the sample complexity of passive PAC learning origin-centered linear separators w.r.t. D is at
23

BALCAN L ONG

least
d−1
e



MD (C, 2ǫ)4

1/(d−1).

Applying Lemma 20 gives an Ω(d/ǫ) lower bound. It is known (Long, 1995) that, if for each ǫ,
there is a pair of classifier v, w such that dD (v, w) = ǫ, then the sample complexity of PAC learningis Ω((1/ǫ) log(1/δ)); this requirement is satisfied by D.
Now let us consider the sample complexity of active learning. As shown in (Kulkarni et al.,1993), in order to output a hypothesis of error at most ǫ with probabality at least 1 − δ, whereδ ≤ 1/2 and active learning algorithm that is allowed to make arbitrary yes-no queries must makeΩ(log MD (C, ǫ)) queries. Using this together with Lemma 20 we get the desired result.

Appendix F. The inseparable case: Disagreement-based active learning
Theorem 14. Let β ≥ 0 be a sufficiently small constant. Assume that D is an isotropic β logβconcave distribution in Rd . For any w∗ , for any ǫ, capw∗ ,D (ǫ) is O(d1/2+ 2 ln 2 log(1/ǫ)). Thusβdisw∗ ,D (ǫ) = O(d1/2+ 2 ln 2 log(1/ǫ)).
Proof Roughly, we will show that almost all x classified by a large enough margin by w∗ are not in
DIS(B(w∗ , r)), because all hypotheses agree with w∗ about how to classify such x, and therefore
all pairs of hypotheses agree with each other. Consider w such that d(w, w∗ ) ≤ r; by Theorem 11∗
β⌈log2 (d+1)⌉ as in the proof of Theorem 11. For any x such
we have θ(w,√ w ) ≤ cr. Define C = ethat ||x|| ≤ dC log(1/r) we have(w · x − w∗ · x) < ||w − w∗ || × ||x||√≤ cr dC log(1/r).
√
Thus, if x also satisfies |w∗ · x| ≥ cr dC log(1/r) we have (w∗ · x)(w · x) > 0. Since this is true
for all w, any such x is not in DIS(B(h, r)). By Theorem 11 we have, for a constant c2 , that√√
Px∼D (|w∗ · x| ≤ cr Cd log(1/r)) ≤ c2 r Cd log(1/r).
Moreover, by Theorem 11 we also have√
Px∼D [||x|| ≥ cr Cd log(1/r)] ≤ r.
√
These both imply capw∗ ,D (ǫ) = O(C 1/2 d log(1/ǫ)).

Appendix G. Massart and Tsybakov noise
In this section we analyze label complexity for active learning under the popular Massart and Tsybakov noise conditions, proving Theorem 15.
We consider a variant of the Tsybakov noise condition (Mammen and Tsybakov, 1999). We
assume that the classifier h that minimizes P(x,y)∼DXY (h(x) 6= y) is a linear classifier, and that, for
24

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

the weight vector w∗ of that optimal classifier, there exist known parameters α, a > 0 such that, for
all w, we havea(dD (w, w∗ ))1/(1−α) ≤ err(w) − err(w∗ ).

(12)

By generalizing Theorem 4 so that it provides a stronger bound for larger margins, and combining the result with the other lemmas of this paper and techniques from (Balcan et al., 2007), we get
the following.
Theorem 15. Let s = O(log(1/ǫ)). Assume that the distribution DXY satisfies the Tsybakovnoise condition for constants α ∈ [0, 1) and a ≥ 0, and that the marginal D on R d is isotropic
log-concave. (1) If α = 0, we can find a separator with excess error ≤ ǫ with probability
1 − δ

d+log(1/δ)
using O(log(1/ǫ))(d+log(s/δ)) labeled examples in the active learning model, and Oǫlabeled examples in the passive learning model. (2) If α > 0, we can find a separator with excess
error ≤ ǫ with probability 1 − δ using O((1/ǫ)2α log2 (1/ǫ))(d + log(s/δ)) labeled examples in theactive learning model.
Note that the case where α = 0 is more general than the well-known Massart noise condition(Massart and Nedelec, 2006). In this case, for active learning, Theorem 15 improves over the previously best known results (Hanneke and Yang, 2012) by a (disagreement coefficient) disw∗ ,D (ǫ)
factor. For passive learning, the bound on the total number of examples needed improves bylog(capw∗ ,D (ǫ)) factor the previously known best bound of (Giné and Koltchinskii, 2006). It is consistent with recent lower bounds of (Raginsky and Rakhlin, 2011) that include log(capw∗ ,D (ǫ)) because those bounds are for a worst-case domain distribution, subject to a constraint on capw∗ ,D (ǫ).
When α > 0, the previously best result for active learning (Hanneke and Yang, 2012) isO((1/ǫ)2α disw∗ ,D (ǫ)(d log(disw∗ ,D (ǫ)) + log(1/δ)).
Combining this with our new bound on disw∗ ,D (ǫ) (Theorem 14) we get a bound ofO((1/ǫ)2α d3/2 log(1/ǫ)(log(d) + log log(1/ǫ)) + log(1/δ))√for log-concave distributions. So our Theorem 15 saves roughly a factor of d, at the expense ofan extra log(1/ǫ) factor.
We note that the results in this section can also be extended to nearly log-concave distributions bymaking use of our results in Section 6.1.
G.1. Proof of Theorem 15
We are now ready to discuss the proof of Theorem 15. As in (Balcan et al., 2007), we will use a
different algorithm in the inseparable case (Algorithm 2).
G.1.1. M ASSART NOISE (α = 0)
We start by analyzing Algorithm 2 in the case that α = 0; the resulting assumption is more generalthan the well-known Massart noise condition.
From the log-concavity assumption, the proof of Theorem 5, with slight modifications, provesthat there exists c such that for all w we havecaθ(w, w∗ ) ≤ err(w) − err(w∗ ).
25

(13)

BALCAN L ONG

Algorithm 2 Margin-based Active Learning (non-separable case)
Input: a sampling oracle for D, and a labeling oracle a sequence of sample sizes mk > 0, k ∈ Z + ;a sequence of cut-off values bk > 0, k ∈ Z + a sequence of hypothesis space radii rk > 0, k ∈ Z + ;a sequence of precision values ǫk > 0, k ∈ Z +Output: weight vector ŵs .
• Pick random ŵ0 : kŵ0 k2 = 1.
• Draw m1 examples from DX , label them and put into W .
– iterate k = 1, . . . , s∗ find ŵ
minimize training error:
Pk ∈ B(ŵk−1 , rk ) (kŵk k2 = 1) to approximately
P(x,y)∈W I(ŵk · xy) ≤ minw∈B(ŵk−1 ,rk )(x,y)∈W I(w · xy) + mk ǫk .
∗ clear the working set W∗ until mk+1 additional data points are labeled, draw sample x from DX· if |ŵk · x| ≥ bk , reject x· otherwise, ask for label of x, and put into W
end iterate

We prove by induction on k that after k ≤ s iterations, we haveerr(ŵk ) − err(w∗ ) ≤ ca2−kP1with probability 1 − 2δ i<k (1+s−i)
2 . The case k = 1 follows from classic bounds (Vapnik, 1998).
Assume now the claim is true for k − 1 (k ≥ 2). Then at the k-th iteration, we can let S1 = {x :|ŵk−1 · x| ≤ bk−1 } and S2P= {x : |ŵk−1 · x| > bk−1 }. By induction hypothesis, we know that with1δ−(k−1) , implying,probability at least 1 − 2 i<k−1 (1+s−i)
2 ŵk−1 has excess errors at most ca2
using (13), that θ(ŵk−1 , w∗ ) ≤ 2−(k−1) . By assumption, θ(ŵk−1 , ŵk ) ≤ 2−(k−1) .
From Theorem 4, recalling that a is a constant, we have both:P((ŵk−1 · x)(ŵ · x) < 0, x ∈ S2 ) ≤ ca2−k /4P((ŵk−1 · x)(w∗ · x) < 0, x ∈ S2 ) ≤ ca2−k /4.
Taking the sum, we obtain:
P((ŵ · x)(w∗ · x) < 0, x ∈ S2 ) ≤ ca2−k /2.
Therefore:err(ŵk ) − err(w∗ ) ≤+≤+(err(ŵk |S1 ) − err(w∗ |S1 ))P(S1 )P((ŵ · x)(w∗ · x) < 0, x ∈ S2 )(err(ŵk |S1 ) − err(w∗ |S1 ))c3 bk−1
ca2−k /2.

By standard Vapnik-Chervonenkis bounds, we can choose C s.t. with mk samples, we obtainerr(ŵk |S1 ) − err(w∗ |S1 ) ≤ ca2−k /(c3 bk−1 )
26

(14)

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

with probability
1 − (δ/2)/(1 + s − i)2 . Therefore err(ŵk ) − err(w∗ ) ≤ ca2−k with probability1δ P
1 − 2 i<k (1+s−i)2 , as desired.
The bound on the total number of examples, labeled and unlabeled, follows the same line ofargument as Theorem 6, except with the constants of this analysis.
G.1.2. T SYBAKOV NOISE (α > 0)
We now treat the more general Tsybakov noise.
For this analysis, we need a generalization of Theorem 4 that provides a stronger bound on theprobably of large-margin errors, using a stronger assumption on the margin.
Theorem 21 There is a positive constant c such that the following holds. Let u and v be two unit
vectors in Rd , and assume that θ(u, v) = η < π/2. Assume that D is isotropic log-concave in Rd .
Then, for any b ≥ cη, we have
Px∼D [sign(u · x) 6= sign(v · x) and |v · x| ≥ b] ≤ C5 η exp(−C6 b/η),(15)

for absolute constants C5 and C6 .
Proof Arguing as in the proof of Lemma 3, we may assume without loss of generality that d = 2.
Next, we claim that each member x of E has ||x|| ≥ b/η. Assume without loss of generalitythat v · x is positive. (The other case is symmetric.) Then u · x < 0, so the angle of x with u is
obtuse, i.e. θ(x, u) ≥ π/2. Since θ(u, v) = η, this implies that
θ(x, v) ≥ π/2 − η.

(16)

But x·v ≥ b, and v is unit length, so ||x|| cos θ(x, v) ≥ b, which, using (16), implies ||x|| cos(π/2−η) ≥ b, which, since cos(π/2 − η) ≤ η for all η ∈ [0, π/2], in turn implies ||x|| ≥ b/η. This implies
that, if B(r) is a ball of radius r in R 2 , that
P[E] =∞X
i=1

P[E ∩ (B((i + 1)(b/η)) − B(i(b/η)))].

(17)

Let us bound one of the terms in RHS. Choose i ≥ 1.
Let f (x1 , x2 ) be the density of D. We haveP[E ∩ (B((i + 1)(b/η)) − B(i(b/η)))]Z
1E (x1 , x2 )f (x1 , x2 ) dx1 dx2 .
=(x1 ,x2 )∈B((i+1)(b/η))−B(i(b/η))Let Ri = B((i + 1)(b/η)) − B(i(b/η). Applying the density upper bound from Lemma 2 withd = 2, there are constants C1 and C2 such thatP[E ∩ (B((i + 1)(b/η)) − B(i(b/η)))]Z≤
1E (x1 , x2 )C1 exp(−(b/η)C2 i)dx1 dx2(x1 ,x2 )∈Ri

= C exp(−(b/η)C2 i) ·Z 1
1E (x1 , x2 ) dx1 dx2 .
(x1 ,x2 )∈Ri

27

BALCAN L ONG

If we include B(i(b/η)) in the integral again, we get
P[E ∩ (B((i + 1)(b/η)) − B(i(b/η)))]Z≤ C1 exp(−(b/η)C2 i)

1E (x1 , x2 ) dx1 dx2 .

(x1 ,x2 )∈B((i+1)(b/η))Now, we exploit the fact that the integral above is a rescaling of a probability with respect to theuniform distribution. Let C3 be the volume of the unit ball in R 2 . Then, we haveP[E ∩ (B((i + 1)(b/η)) − B(i(b/η)))]≤ C1 exp(−(b/η)C2 i)C3 (i + 1)2 (b/η)2 η/π= C4 (b/η)2 η(i + 1)2 exp(−(b/η)C2 i),
for C4 = C1 C3 /π. Returning to (17), we get
P[E] =∞X

C4 (b/η)2 η(i + 1)2 exp(−(b/η)C2 i)

i=12= C4 (b/η) η∞X(i + 1)2 exp(−(b/η)C2 i)

i=1= C4 (b/η)2 ×
Now, if b/η > 4/C2 , we have
P[E] ≤ C4 (b/η)2 ×

4e2(b/η)C2 − 3e(b/η)C2 + 1× η.
3e(b/η)C2 − 1

5e2(b/η)C2
3 × η
e(b/η)C2 /2≤ C5 η × (b/η)2 exp(−(b/η)C2 )(where C5 = 40C4 )= C5 η × exp(−(b/η)C2 + 2 ln(b/η))≤ C5 η × exp(−(b/η)C2 /2),
completing the proof.
Now we are ready to prove Theorem 15 in the case that α > 0.
Under the noise condition 12 and from the log-concavity assumption, we obtain that there exists
c such that for all w we have:ac1/(1−α) θ(w, w∗ )1/(1−α) ≤ err(w) − err(w∗ ).
Let us denote by c̃ = ac1/(1−α) . For all w, we have:c̃θ(w, w∗ )1/(1−α) ≤ err(w) − err(w∗ ).
We prove by induction on k that after k ≤ s iterations, we haveerr(ŵk ) − err(w∗ ) ≤ c̃2−k
28

(18)

ACTIVE AND PASSIVE LEARNING OF LINEAR SEPARATORS UNDER LOG - CONCAVE DISTRIBUTIONS

P
1with probability 1 − δ2 i<k (1+s−i)
2 . The case k = 1 follows from classic bounds.
Assume now the claim is true for k − 1 (k ≥ 2). Then at the k-th iteration, we can let S1 ={x : |ŵk−1 · x| ≤ bk−1 } and S2 =P{x : |ŵk−1 · x| > bk−1 }. By the induction hypothesis, we know1−(k−1)(1−α) ,that with probability at least 1 − δ i<k−1 (1+s−i)
2 , ŵk−1 has excess errors at most c̃2
implying
θ(ŵk−1 , w∗ ) ≤ 2−(k−1)(1−α) .
By assumption, θ(ŵk−1 , ŵk ) ≤ 2−(k−1)(1−α) .
Applying Theorem 21, we have both:P((ŵk−1 · x)(ŵ · x) < 0, x ∈ S2 ) ≤ c̃2−k /4P((ŵk−1 · x)(w∗ · x) < 0, x ∈ S2 ) ≤ c̃2−k /4
Taking the sum, we obtain:
P((ŵ · x)(w∗ · x) < 0, x ∈ S2 ) ≤ c̃2−k /2.

(19)

Therefore:err(ŵk ) − err(w∗ ) ≤ (err(ŵk |S1 ) − err(w∗ |S1 ))P(S1 )+P((ŵ · x)(w∗ · x) < 0, x ∈ S2 )≤ (err(ŵk |S1 ) − err(w∗ |S1 ))bk+c̃2−k /2.
By standard bounds, we can choose C1 , C2 and C3 s.t. with mk samples, we obtain err(ŵk |S1 )−−kerr(w∗ |S1 ) ≤ ǫk ≤ c̃22bk with probability 1 − (δ/2)/(1 + s − i)2 . Therefore err(ŵk ) − err(w∗ ) ≤P1c̃2−k with probability 1 − 2δ i<k (1+s−i)
2 , as desired, completing the proof of Theorem 15.

29