Adam R. Klivans¹*, Philip M. Long², and Alex K. Tang³ 1 UT-Austin, klivans@cs.utexas.edu ² Google, plong@google.com 3 UT-Austin, tang@cs.utexas.edu Abstract.  In 1990, E. Baum gave an elegant polynomial-time algorithm for learning the intersection of two origin-centered halfspaces with respect to any symmetric distribution (i.e., any D such that D(E) = D( − E)) [3]. Here we prove that his algorithm also succeeds with respect to any mean zero distribution D with a log-concave density (a broad class of distribu- tions that need not be symmetric). As far as we are aware, prior to this work, it was not known how to efficiently learn any class of intersections of halfspaces with respect to log-concave distributions. The key to our proof is a "Brunn-Minkowski" inequality for log-concave densities that may be of independent interest.
1
Introduction
A function f : R n → R is called a linear threshold function or halfspace if f ( x ) = sgn( w · x ) for some vector w ∈ R n . Algorithms for learning halfspaces from labeled examples are some of the most important tools in machine learning. While there exist several efficient algorithms for learning halfspaces in a variety of settings, the natural generalization of the problem — learn- ing the intersection of two or more halfspaces (e.g., the concept class of functions of the form h = f ∧ g where f and g are halfspaces) — has remained one of the great challenges in computational learning theory. In fact, there are no nontrivial algorithms known for the problem of PAC learning the intersection of just two halfspaces with respect to an arbitrary distribution. As such, several researchers have made progress on restricted versions of the problem. Baum provided a simple and elegant algorithm for learning the intersection of two origin-centered halfspaces with respect to any symmetric distribution on R n [3]. Blum and Kannan [4] and Vempala [16] designed polynomial-time algorithms for learning the intersection of any constant number of halfspaces with respect to the uniform distribution on the unit sphere in R n . Arriaga and Vempala [2] and Klivans and Servedio [13] designed algorithms for learning a constant number of halfspaces given an assumption that the support of the positive and negative regions in feature space are separated by a margin. The best bounds grow with the margin γ like (1/γ)O(log(1/γ))
1.1
Log-Concave Densities
In this paper, we significantly expand the classes of distributions for which we can learn intersections of two halfspaces: we prove that Baum's algo- rithm succeeds with respect to any mean zero, log-concave probability distribution. We hope that this is a first step towards finding efficient algorithms that can handle intersections of many more halfspaces with respect to a broad class of probability distributions. A distribution D is log-concave if it has a density f such that log f( · ) is a concave function. Log-concave distributions are a powerful class that capture a range of interesting scenarios: it is known, for example, that the uniform distribution over any convex set is log-concave (if the convex set is centered at the origin, then the corresponding density has mean zero). Hence, Vempala's result mentioned above works for a very special case of log-concave distributions (it is not clear whether his algorithm works for a more general class of distributions). Additionally, interest in log-concave densities among machine learning researchers has been growing of late [10, 7, 1, 9, 14]. There has also been some recent work on learning intersections of halfspaces with respect to the Gaussian distribution on R n , another spe- cial case of a log-concave density. Klivans et al. have shown how to learn (even in the agnostic setting) the intersection of a constant number of halfspaces to any constant error parameter in polynomial-time with re- spect to any Gaussian distribution on R n [12]. Again, it is unclear how to extend their result to log-concave distributions.
1.2
Our approach: Re-analyzing Baum's Algorithm
In this paper, we prove that Baum's algorithm from 1990 succeeds when the underlying probability distribution is not necessarily symmetric, but is log-concave. Baum's algorithm works roughly as follows. Suppose the unknown target concept C is the intersection of the halfspace H u defined by u x ≥ 0 and the halfspace H v defined by v x ≥ 0. Note that if x ∈ C then (u · x )(v · x ) ≥ 0, so that
If we replace the original features x 1 , . . . , x n with all products x ix j of pairs of features, this becomes a linear inequality. The trouble is that ( u·x )( v·x ) is also positive if x ∈ −C , i.e., both u · x ≤ 0 and v · x ≤ 0. The idea behind Baum’s algorithm is to eliminate all the negative examples in −C by identifying a region N in the complement of C (the "negative" region) that, with high probability, includes almost all of − C . Then, Baum finds a halfspace in an expanded feature space that is consistent with rest of the examples. (See Figure 1). To compute N , Baum finds a halfspace H ′ containing a large set of positive examples in C , and then sets N = −H ′ . Here is where he uses the assumption that the distribution is symmetric: he reasons that if H ′ contains a lot of positive examples, then H ′ contains most of the measure of C , and, since the distribution is symmetric, − H ′ contains most of the measure of − C . Then, if he draws more examples and excludes those in −H ′ , he is unlikely to obtain any examples in −C , and for each example x that remains, (1) will hold only if and only if x ∈ C . The output hypothesis classifies an example falling in N negatively, and uses the halfspace in the expanded feature space to classify the remaining examples. We extend Baum's analysis by showing that, if the distribution is centered and log-concave, then the probability of the region in − C that fails to be excluded by –H' is not much larger than the probability of that part of C that is not covered by H ′ . Thus, if H ′ is trained with somewhat more examples, the algorithm can still ensure that –H' fails to cover a small part of − C . Thus, we arrive at the following natural problem from convex geom- etry: given a cone K whose apex is at the origin in R n , how does Pr(K) relate to Pr( − K ) for distributions whose density is log-concave? Were the distribution uniform over a convex set centered at the origin, we could use the Brunn-Minkowski theory to argue that Pr(K) is always within a factor of n times Pr( − K ) (see the discussion after the proof of Lemma 6). Instead, we are working with a mean zero log-concave distribution, and we do not know of an analog of the Brunn-Minkowski inequality for log-concave densities. Instead, we make use of the fact that the cones we are interested in are very simple and can be described by the intersection of just three halfspaces, and show that Pr(K) is within a constant fac- tor of Pr( − K ). Proving this makes use of tools for analyzing log-concave densities provided by Lovász and Vempala [14].
2
Preliminaries
2.1
VC Theory and sample complexity
We shall assume the reader is familiar with basic notions in computa- tional learning theory such as Valiant's PAC model of learning and VC- dimension (see Kearns & Vazirani for an in-depth treatment [11]). Theorem 1 ([15,6]). Let C be a class of concepts from the set X to {−1,1} whose VC dimension is d. Let c ∈ C, and suppose
examples x 1 , . . . , x м  are  drawn  according to  any  probability  distribution D over X . Then, with probability at least 1 – δ, any hypothesis h ∈ C that is consistent with c on x 1 , . . , x M has error at most ε w.r.t. D. Lemma 1. The class of origin-centered halfspaces over R n has VC di- mension n. Lemma 2. Let C be a class of concepts from the set X to {−1,1}. Let X' be a subset of X , and let C' be the class of concepts in C restricted to X'; in other words, let
Then, the VC dimension of C' is at most the VC dimension of C.
2.2
Log-concave densities
Definition 1 (isotropic, log-concave). A probability density function f over R n is log-concave if log f ( · ) is concave. It is isotropic if the co- variance matrix of the associated probability distribution is the identity. We will use a number of facts that were either stated by Lovász and Vempala, or are easy consequences of their analysis. Lemma 3 ([14]). Any halfspace containing the origin has probability at least 1/e under a log-concave distribution with mean zero. Lemma 4 ([14]). Suppose f is an isotropic, log-concave probability den- sity function over Rn. Then, (a) f (0) ≥ 2–7n. (b) f (0) ≤ n(20n)n/2 (c)  f(x) ≥ 2−7n2−9n‖x‖ whenever 0 ≤ ‖x‖ ≤ 1/9. (d) f(x) ≤ 28nnn/2 for every x ∈ Rn. (e) For every line ℓ through the origin, ſ ℓ f ≤ (n − 1)(20(n − 1))(n−1)/2 Proof. Parts a-d are immediate consequences of Theorem 5.14 of [14]. The proof of Part e is like the proof of an analogous lower bound in [14]. Change the basis of R n so that ℓ is the x n -axis, and let h be the marginal over the first n – 1 variables. Then, by definition,
so that h(0) = f f . Applying the inequality of Part b gives Part e. □
3
Baum’s Algorithm
Let H u and H v be the two origin-centered halfspaces whose intersection we are trying to learn. Baum's algorithm for learning H u ∩H v is as follows: 1. First, define
where κ is the constant that appears in Lemmas 6 and 7 below. 2. Draw m 3 examples. Let r denote the number of positive examples observed. If r < m2 , then output the hypothesis that labels every point as negative. Otherwise, continue to the next step. 3. Use linear programming to find an origin-centered halfspace H ′ that contains all r positive examples. 4. Draw examples until we find a set S of m 1 examples in H ′ . (Discard examples in –H'.) Then, use linear programming to find a weight vector w ∈ Rn×n such that the hypothesis h xor : Rn → {−1,1} given by
is consistent with all examples in S . 5. Output the hypothesis h : R n → { − 1, 1} given by
Outline of proof. In Theorem 2, we prove that Baum's algorithm learns H u ∩ H v in the PAC model, when the distribution on R n is log-concaved and has mean zero. Here we give an informal explanation of the proof. In step 3, the algorithm finds a halfspace H ′ that contains all but a small fraction of the positive examples. In other words, Pr(H n ∩ H n ∩ (−H')) is small. This implies that points in –H' have a small chance of being positive, so we can just classify them as negative. To classify points in H ′ , the algorithm learns a hypothesis hxor in step 4. We must show that hxor is a good hypothesis for points in H ′ . Under a log-concave distribution with mean zero, for any intersection of three halfspaces, its probability mass is at most a constant times the probability of its reflection about the origin; this is proved in Lemma 7. In particular,
for some constant κ > 0. Therefore, since Pr( H ν H ν ∩ (−H ′ )) is small, we can conclude that Pr((-H u ) ∩ (-H v ) ∩ H ′ ) is also small. This implies that, with high probability, points in H ′ will not lie in ( − H u ) ∩ ( − H v ); thus, they must lie in H u ∩ H v , H v ∩ (− H v ), or (− H v ) ∩ H v . Such points are classified according to the symmetric difference H v △ H v restricted to H ′ . (Strictly speaking, the points are classified according to the negation of the concept H u △ H v restricted to H ′ ; that is, we need to invert the labels so that positive examples are classified as negative and negative examples are classified as positive.) By Lemmas 1 and 2, together with the fact that hxor can be interpreted as a halfspace over Rn 2 , the class of such concepts has VC dimension at most n 2 . Hence, we can use the VC Theorem to conclude that the hypothesis h xor has low error on points in H'. Now, we describe the strategy for proving (2). In Lemma 7, we prove that Pr( − R ) < κ Pr( R ), where R is the intersection of any three origin- centered halfspaces. This inequality holds when the probability distribu- tion is log-concave and has mean zero. First, we prove in Lemma 6 that the inequality holds for the special case when the log-concave distribution not only has mean zero, but is also isotropic. Then, we use Lemma 6 to prove Lemma 7. We consider Lemma 7 to be a Brunn-Minkowski-type inequality for log-concave distributions (see the discussion after the proof of Lemma 6). To prove Lemma 6, we will exploit the fact that, if R is defined by an intersection of three halfspaces, the probability of R is the same as the probability of R with respect to the marginal distribution over examples projected onto the subspace of R n spanned by the normal vectors of the halfspaces bounding R — this is true, roughly speaking, because the dot products with those normal vectors are all that is needed to determine membership in R , and those dot products are not affected if we project onto the subspace spanned by those normal vectors. The same holds, of course, for – R. Once we have projected onto a 3-dimensional subspace, we perform the analysis by proving upper and lower bounds on the probabilities of R and – R , and showing that they are within a constant factor of one an- other. We analyze the probability of R (respectively − R ) by decomposing it into layers that are varying distances r from the origin. To analyze each layer, we will use upper and lower bounds on the density of points at a dis- tance r . Since the sizes (even the shapes) of the regions at distance r are the same for R and – R , if the densities are close, then the probabilities must be close. Lemma 5 provides the upper bound on the density in terms of the distance (the lower bound in Lemma 4c suffices for our purposes). We only need the bound in the case n = 3, but we go ahead and prove a bound for all n . Kalai, Klivans, Mansour, and Servedio prove a one-dimensional version in Lemma 6 of [9]. We adapt their proof to the n-dimensional case. Lemma 5. Let f : Rn → R+ be an isotropic, log-concave probability density function. Then, f(x) ≤ β1e-β2llxll for all x ∈ Rn, where β1 := 28nnn/2e and β2 := 2(n-1)(20(n-1))(n-1)/2 Proof. We first observe that if ‖ x ‖ ≤ 1/β 2 , then β 1 e−β 2 ‖ x ‖ ≥ β 1 e−1 = 28nnn/2. By Lemma 4d, f(x) ≤ β1e-β2ll×ll if ∥ x ∥ ≤ 1/β2. Now, assume there exists a point v ∈ R n such that ∥ v ∥ > 1/β 2 and f ( v ) > β 1 e −β 2 ∥ v ∥ We shall show that this assumption leads to a contradiction. Let [0, v] denote the line segment between the origin 0 and v . Every point x ∈ [0, v] can be written as a convex combination of 0 and v as follows: x = (1 — ||x||/||v||)0 + (||x||/||v||)v. Therefore, the log-concavity of f implies that
We assumed that f(v) > β1e-β2llvll. So Lemma 4a implies
Because 2-7n < 1 and 1 - ||x||/||v|| < 1, we know that (2-7n)1-||x||/||v|| 2-7n. Because β 1 ≥ 1, we know that β 1 x 1 / 1 v 1 ≥ 1. We can therefore conclude that f(x) > 2-7ne-B2llxll. Integrating over the line ℓ through 0 and v, we get
Now we are ready for Lemma 6, which handles the isotropic case. Lemma 6.  Let R be the intersection of three origin-centered halfspaces in R n . Assume that the points in R n are distributed according to an isotropic, log-concave probability distribution. Then, Pr(–R) ≤ κ Pr(R) for some constant κ > 0. Proof. Let u 1 , u 2 , and u 3 be normals to the hyperplanes that bound the region R. Then, R = { x ∈ R n | u 1 · x ≥ 0 and u 2 · x ≥ 0 and u 3 · x ≥ 0}. Let U be the linear span of u 1 , u 2 , and u 3 . Choose an orthonormal basis (e 1 , e 2 , e 3 ) for U and extend it to an orthonormal basis (e 1 , e 2 , e 3 , . . . , e n ) for all of R n . Write the components of the vectors x , u 1 , u 2 , and u 3 in terms of this basis:
Let projU(x) denote the projection of x onto U ; that is, let projU(x) := ( x 1 , x 2 , x 3 ). Likewise, let proj U ( R ) denote the projection of R onto U ; that is, let proj U ( R ) := {proj U ( x ) | x ∈ R } . Observe that
Let f denote the probability density function of the isotropic, log-concaver probability distribution on R n . Let g be the marginal probability density function with respect to (x 1 , x 2 , x 3 ); that is, define
Then, it follows from (3) that
Note that q is isotropic and log-concave, because the marginals of an isotropic, log-concave probability density function are isotropic and log- concave (see [14, Theorem 5.1, Lemma 5.2]). Thus, we can use Lemma 4c and Lemma 5 to bound g . The bounds don't depend on the dimension n, because g is a probability density function over R 3 . For brevity of notation, let y := (x 1 , x 2 , x 3 ). By Lemma 4c, there exist constants κ 1 and κշ such that
And by Lemma 5, there exist constants κ 3 and κ 4 such that
Let R' := proj U (R) ∩ B (0,1/9), where B (0,1/9) denotes the origin- centered ball of radius 1/9 in R 3 . Use (4) and (5) to derive the following lower and upper bounds:
Recall that
Now, we transform the integrals in the lower and upper bounds in (6) to spherical coordinates. The transformation to spherical coordinates is given by r := √ y 2 + y 2 + y 3 , ϕ := arctan( N ), θ := arccos √ｼﾞｷ+ｼﾞｼﾞｷﾋﾞｼﾞ The determinant of the Jacobian of the above transformation is known to be r 2 sin ϑ [5]. Thus (see [5]), inequality (6) becomes
Let A denote the surface area of the intersection of proj U ( R ) with the unit sphere S²; that is, let
Then, it follows that
If we let
□ If the distribution were uniform over a convex set K whose centroid is at the origin, then the proof of Lemma 6 could be modified to show that the probabilities of R and − R are within a factor of n without requiring that R is the intersection of three halfspaces; we would only need that R is a cone (closed under positive rescaling). This could be done by observing that the probability of R is proportional to the average distance of a ray contained in R to the boundary of K . Then we could apply the Brunn-Minkowski inequality (see [8, Lemma 29]) which states that for any direction x , the distance from the origin to the boundary of K in the direction of x is within a factor n of the distance to the boundary of K in the direction – x . In Lemma 6, we assumed that the distribution is isotropic. The next lemma shows that this assumption can be removed (provided that the mean of the distribution is still zero). A key insight is that, under a linear transformation, the image of the intersection of three halfspaces is another intersection of three halfspaces. To prove the lemma, we use a particular linear transformation that brings the distribution into isotropic position. Then, we apply Lemma 6 to the transformed distribution and the image of the three-halfspace intersection. Lemma 7. Let R be the intersection of three origin-centered halfspaces in R n . Assume that the points in R n are distributed according to a log- concave probability distribution with mean zero. Then, Pr( − R ) ≤ κ Pr( R ), where κ is the same constant that appears in Lemma 6. Proof. Let X be a random variable in R n with a mean-zero, log-concave probability distribution. Let V denote the convariance matrix of X . Let W be a matrix square root of the inverse of V ; that is, W 2 = V −1 . Then, the random variable Y := W X is log-concave and isotropic. (Technically, if the rank of the convariance matrix V is less than n , then V would not be invertible. But, in that case, the probability distribution degenerates into a probability distribution over a lower-dimensional subspace. We just repeat the analysis on this subspace.) Let W(R) and W( − R) respectively denote the images of R and − R under W . Notice that W ( − R ) = − W ( R ). Also, notice that X ∈ R ↔ Y ∈ W(R) and that X ∈ −R ↔ Y ∈ W(−R) = −W(R). Let u 1 , u 2 , and u 3 be normals to the hyperplanes that bound R. Then,
Therefore, W(R) is the intersection of three origin-centered halfspaces, so we can apply Lemma 6 to obtain
Finally, we analyze Baum's algorithm using the probability bound given in Lemma 7. Theorem 2. In the PAC model, Baum's algorithm learns the intersec- tion of two origin-centered halfspaces with respect to any mean zero, log- concave probability distribution in polynomial time. Proof. If the probability p of observing a positive example is less than ε , then the hypothesis that labels every example as negative has error less than ε ; so the algorithm behaves correctly if it draws fewer than m2 positive examples in this case. If p ≥ ε , then by the Hoeffding bound,
Thus, if p ≥ ε , then the probability of failing to draw at least m2 positive examples is at most δ/4. For the rest of this proof, we shall assume that the algorithm succeeds in drawing at least m 2 positive examples. Observe that the hypothesis output by the algorithm has error
where c : R n → {−1,1} denotes the concept corresponding to H u ∩ H v . First, we give a bound for
Notice that Pr(−H′ | H u ∩ H v ) is the error of the hypothesis correspond- ing to H ′ over the distribution conditioned on H u ∩ H v . But the VC Theorem works for any distribution, so, since H ′ contains every one of M (max{δ/(4eκm1),ε/2},δ/4,n) random positive examples, it follows from Lemma 1 that, with probability at least 1 – δ/4,
Since Pr(H v ∩ H v ) ≤ 1, it follows that
Therefore, the left term in (7) is at most ε /2. All that remains is to bound the right term. From Lemma 7, it follows that
Thus, each of the m 1 points in S has probability at most δ /4m 1 of being in ( − H v ) ∩ ( − H v ), so with probability at least 1 − δ /4, none of the m 1 points are in ( − H v ) ∩ ( − H v ). Thus, each point in x ∈ S lies in H v ∩ H v , H u ∩ (−H v ), or (−H v ); if x ∈ H u ∩ H v , then x is labeled as positive; if x ∈ H u ∩ (−H v ) or x ∈ (−H v ) ∩ H v , then x is labeled as negative. In other words, the points in S are classified according to the negation of H u △H v restricted to the halfspace H ′ . Thus, the linear program executed in Step 4 successfully finds a classifier h xor consistent with the examples in S . By Lemma 1 and Lemma 2, the class of symmetric differences of origin-centered halfspaces restricted to H ′ has VC dimension at most n 2 . Therefore, the VC Theorem implies that, with probability at least 1 – δ /4,
Since Pr(H ′ ) ≤ 1, the right term in (7) is at most ε /2. Adding up the probabilities of the four ways in which the algorithm can fail, we concluded that the probability that err(h) > ε is at most 4(δ/4) = δ. □