Journal of Machine Learning Research 14 (2013) 3073-3096

Submitted 1/12; Revised 4/13; Published 10/13

Algorithms and Hardness Results for Parallel Large Margin Learning
Philip M. LongPLONG @ MICROSOFT. COM

Microsoft
1020 Enterprise Way
Sunnyvale, CA 94089

Rocco A. Servedio

ROCCO @ CS . COLUMBIA . EDU

Department of Computer Science
Columbia University
1214 Amsterdam Ave., Mail Code: 0401
New York, NY 10027

Editor: Yoav Freund

Abstract
We consider the problem of learning an unknown large-margin halfspace in the context of parallel
computation, giving both positive and negative results.
As our main positive result, we give a parallel algorithm for learning a large-margin halfspace, based on an algorithm of Nesterov’s that performs gradient descent with a momentum term.
We show that this algorithm can learn an unknown γ-margin halfspace over n dimensions usingn · poly(1/γ) processors and running in time Õ(1/γ) + O(log n). In contrast, naive parallel algorithms that learn a γ-margin halfspace in time that depends polylogarithmically on n have an inverse
quadratic running time dependence on the margin parameter γ.
Our negative result deals with boosting, which is a standard approach to learning large-margin
halfspaces. We prove that in the original PAC framework, in which a weak learning algorithm isprovided as an oracle that is called by the booster, boosting cannot be parallelized. More precisely,
we show that, if the algorithm is allowed to call the weak learner multiple times in parallel within
a single boosting stage, this ability does not reduce the overall number of successive stages ofboosting needed for learning by even a single stage. Our proof is information-theoretic and does
not rely on unproven assumptions.
Keywords: PAC learning, parallel learning algorithms, halfspace learning, linear classifiers

1. Introduction
One of the most fundamental problems in machine learning is learning an unknown halfspace fromlabeled examples that satisfy a margin constraint, meaning that no example may lie too close to theseparating hyperplane. In this paper we consider large-margin halfspace learning in the PAC (probably approximately correct) setting of learning from random examples: there is a target halfspacef (x) = sign(w · x), where w is an unknown unit vector, and an unknown probability distribution D
over the unit ball Bn = {x ∈ Rn : kxk2 ≤ 1} which is guaranteed to have support contained in the set{x ∈ Bn : |w · x| ≥ γ} of points that have Euclidean margin at least γ relative to the separating hyperplane. (Throughout this paper we refer to such a combination of target halfspace f and distribution
D as a γ-margin halfspace.) The learning algorithm is given access to labeled examples (x, f (x))
c 2013 Philip M. Long and Rocco A. Servedio.

L ONG AND S ERVEDIO

where each x is independently drawn from D , and it must with high probability output a (1 − ε)accurate hypothesis, that is, a hypothesis h : Rn → {−1, 1} that satisfies Prx∼D [h(x) 6= f (x)] ≤ ε.
One of the earliest, and still most important, algorithms in machine learning is the perceptron
algorithm (Block, 1962; Novikoff, 1962; Rosenblatt, 1958) for learning a large-margin halfspace.
The perceptron is an online algorithm but it can be easily transformed to the PAC setting describedabove (Vapnik and Chervonenkis, 1974; Littlestone, 1989; Freund and Schapire, 1999); the resulting
PAC algorithms run in poly(n, 1γ , 1ε ) time, use O( εγ12 ) labeled examples in Rn , and learn an unknown
n-dimensional γ-margin halfspace to accuracy 1 − ε.
A motivating question: achieving perceptron’s performance in parallel? The last few years
have witnessed a resurgence of interest in highly efficient parallel algorithms for a wide range ofcomputational problems in many areas including machine learning (Workshop, 2009, 2011). So
a natural goal is to develop an efficient parallel algorithm for learning γ-margin halfspaces thatmatches the performance of the perceptron algorithm. A well-established theoretical notion ofefficient parallel computation (see, for example, the text by Greenlaw et al. (1995) and the manyreferences therein) is that an efficient parallel algorithm for a problem with input size N is one thatuses poly(N) processors and runs in parallel time polylog(N). Since the input to the perceptron
algorithm is a sample of poly( 1ε , 1γ ) labeled examples in Rn , we naturally arrive at the following:
Main Question: Is there a learning algorithm that uses poly(n, 1γ , 1ε ) processors andruns in time poly(log n, log 1γ , log 1ε ) to learn an unknown n-dimensional γ-margin halfspace to accuracy 1 − ε?
Following Vitter and Lin (1992), we use a CRCW PRAM model of parallel computation. This
abstracts away issues like communication and synchronization, allowing us to focus on the mostfundamental issues. Also, as did Vitter and Lin (1992), we require that an efficient parallel learningalgorithm’s hypothesis must be efficiently evaluatable in parallel, since otherwise all the computation required to run any polynomial-time learning algorithm could be “offloaded” onto evaluating
the hypothesis. Because halfspace learning algorithms may be sensitive to issues of numerical precision, these are not abstracted away in our model; we assume that numbers are represented asrationals.
As noted by Freund (1995) (see also Lemma 2 below), the existence of efficient boostingalgorithms such as the algorithms of Freund (1995) and Schapire (1990) implies that any PAC
learning algorithm can be efficiently parallelized in terms of its dependence on the accuracy parameter ε: more precisely, any PAC learnable class C of functions can be PAC learned to accuracy 1− ε using O(1/ε) processors by an algorithm whose running time dependence on ε isO(log 1ε · poly(log log(1/ε))), by boosting an algorithm that learns to accuracy (say) 9/10. We
may thus equivalently restate the above question as follows.
Main Question (simplified): Is there a learning algorithm that uses poly(n, 1γ ) processors and runs in time poly(log n, log 1γ ) to learn an unknown n-dimensional γ-margin
halfspace to accuracy 9/10?
The research reported in this paper is inspired by this question, which we view as a fundamental
open problem about the abilities and limitations of efficient parallel learning algorithms.

3074

PARALLEL L ARGE -M ARGIN L EARNING

Algorithm
naive parallelization of perceptron(Servedio, 2003)
poly-time linear programming (Blumer et al., 1989)
this paper (algorithm of Section 2)

No. processors
poly(n, 1/γ)
poly(n, 1/γ)
1n · poly(1/γ)

Running timeÕ(1/γ2 ) + O(log n)Õ(1/γ2 ) + O(log n)poly(n, log(1/γ))Õ(1/γ) + O(log n)

Table 1: Bounds on various parallel algorithms for learning a γ-margin halfspace over Rn .
1.1 Relevant Prior Results
Table 1 summarizes the running time and number of processors used by various parallel algorithms
to learn a γ-margin halfspace over Rn .
The naive parallelization of perceptron in the first line of the table is an algorithm that runs forO(1/γ2 ) stages. In each stage it processes all of the O(1/γ2 ) examples simultaneously in parallel,
identifies one that causes the perceptron algorithm to update its hypothesis vector, and performs thisupdate. Since the examples are n-dimensional this can be accomplished in O(log(n/γ)) time usingO(n/γ2 ) processors; the mistake bound of the online perceptron algorithm is 1/γ2 , so this gives arunning time bound of Õ(1/γ2 ) · log n. We do not see how to obtain parallel time bounds better thanO(1/γ2 ) from recent analyses of other algorithms based on gradient descent (Collins et al., 2002;
Dekel et al., 2011; Bradley et al., 2011), some of which use assumptions incomparable in strength
to the γ-margin condition studied here.
The second line of the table corresponds to a similar naive parallelization of the boosting-basedalgorithm of Servedio (2003) that achieves perceptron-like performance for learning a γ-margin
halfspace. This algorithm boosts for O(1/γ2 ) stages over a O(1/γ2 )-size sample. At each stageof boosting this algorithm computes a real-valued weak hypothesis based on the vector average ofthe (normalized) examples weighted according to the current distribution; since the sample size isO(1/γ2 ) this can be done in O(log(n/γ)) time using poly(n, 1/γ) processors. Since the boostingalgorithm runs for O(1/γ2 ) stages, the overall running time bound is Õ(1/γ2 ) · log n. (For both thisalgorithm and the perceptron the time bound can be improved to Õ(1/γ2 ) + O(log n) as claimed in
the table by using an initial random projection step. We show how to do this in Section 2.3.)
The third line of the table, included for comparison, is simply a standard sequential algorithm
for learning a halfspace based on polynomial-time linear programming executed on one processor(Blumer et al., 1989; Karmarkar, 1984).
In addition to the results summarized in the table, we note that efficient parallel algorithms havebeen developed for some simpler PAC learning problems such as learning conjunctions, disjunctions, and symmetric Boolean functions (Vitter and Lin, 1992). Bshouty et al. (1998) gave efficientparallel PAC learning algorithms for some geometric constant-dimensional concept classes. Collins
et al. (2002) presented a family of boosting-type algorithms that optimize Bregman divergences by
updating a collection of parameters in parallel; however, their analysis does not seem to imply thatthe algorithms need fewer than Ω(1/γ2 ) stages to learn γ-margin halfspaces.
In terms of negative results for parallel learning, Vitter and Lin (1992) showed that (undera complexity-theoretic assumption) there is no parallel algorithm using poly(n) processors andpolylog(n) time that constructs a halfspace hypothesis that is consistent with a given linearly separable data set of n-dimensional labeled examples. This does not give a negative answer to the3075

L ONG AND S ERVEDIO

main question for several reasons: first, the main question allows any hypothesis representation thatcan be efficiently evaluated in parallel, whereas the hardness result requires the hypothesis to be ahalfspace. Second, the main question allows the algorithm to use poly(n, 1/γ) processors and to
run in poly(log n, log 1γ ) time, whereas the hardness result of Vitter and Lin (1992) only rules out
algorithms that use poly(n, log 1γ ) processors and run in poly(log n, log log 1γ ) time. Finally, the mainquestion allows the final hypothesis to err on up to (say) 5% of the points in the data set, whereas
the hardness result of Vitter and Lin (1992) applies only to algorithms whose hypotheses correctlyclassify all points in the data set.
Finally, we note that the main question has an affirmative answer if it is restricted so that either
the number of dimensions n or the margin parameter γ is fixed to be a constant (so the resulting
restricted question asks whether there is an algorithm that uses polynomially many processors andpolylogarithmic time in the remaining parameter). If γ is fixed to a constant then either of the firsttwo entries in Table 1 gives a poly(n)-processor, O(log n)-time algorithm. If n is fixed to a constantthen the efficient parallel algorithm of Alon and Megiddo (1994) for linear programming in constantdimension can be used to learn a γ-margin halfspace using poly(1/γ) processors in polylog(1/γ)
running time (see also Vitter and Lin, 1992, Theorem 3.4).
1.2 Our Results
We give positive and negative results on learning halfspaces in parallel that are inspired by the mainquestion stated above.
1.2.1 P OSITIVE R ESULTS
Our main positive result is a parallel algorithm for learning large-margin halfspaces, based on a
rapidly converging gradient method due to Nesterov (2004), which uses O(n · poly(1/γ)) processors
to learn γ-margin halfspaces in parallel time Õ(1/γ) + O(log n) (see Table 1). (An earlier version ofthis paper (Long and Servedio, 2011) analyzed on algorithm based on interior-point methods fromconvex optimization and fast parallel algorithms for linear algebra, showing that it uses poly(n, 1/γ)
processors to learn γ-margin halfspaces in parallel time Õ(1/γ) + O(log n).) We are not aware ofprior parallel algorithms that provably learn γ-margin halfspaces running in time polylogarithmic inn and subquadratic in 1/γ.
We note that simultaneously and independently of the initial conference publication of our work
(Long and Servedio, 2011), SoheiliandPeña (2012) proposed a variant of the perceptron algorithm√
log niterations rather than the 1/γ2 iterations of the originaland shown that it terminates in Oγ
perceptron algorithm. Like our algorithm, the Soheili and Peña (2012) algorithm uses ideas of Nesterov (2005). Soheili and Peña (2012) do not discuss a parallel implementation of their algorithm,
but since their algorithm performs an n-dimensional matrix-vector multiplication at each iteration,2
it appears that a parallel implementation
 of their
 algorithm would use Ω(n ) processors and would
have parallel running time at least Ω(log n)3/2
γ(assuming that multiplying a n × n matrix by ann × 1 vector takes parallel time Θ(log n) using n2 processors). In contrast, our algorithm requires alinear number of processors as a function of n, and has parallel running time Õ(1/γ) + O(log n).1

1. We note also that Soheili and Peña (2012) analyze the number of iterations of their algorithm, and not the computation
time. In particular, they do not deal with finite precision issues, whereas a significant portion of our analysis concerns

3076

PARALLEL L ARGE -M ARGIN L EARNING

1.2.2 N EGATIVE R ESULTS
By modifying our analysis of the algorithm we present, we believe that it may be possible to establish similar positive results for other formulations of the large-margin learning problem, includingones (see Shalev-Shwartz and Singer, 2010) that have been tied closely to weak learnability. In
contrast, our main negative result is an information-theoretic argument that suggests that such positive parallel learning results cannot be obtained by boosting alone. We show that in a framework
where the weak learning algorithm must be invoked as an oracle, boosting cannot be parallelized:
being able to call the weak learner multiple times in parallel within a single boosting stage does not
reduce the overall number of sequential stages of boosting that are required. We prove that any parallel booster must perform Ω(log(1/ε)/γ2 ) sequential stages of boosting a “black-box” γ-advantage
weak learner to learn to accuracy 1 − ε in the worst case; this extends an earlier Ω(log(1/ε)/γ2 )lower bound of Freund (1995) for standard (sequential) boosters that can only call the weak learner
once per stage.

2. An Algorithm Based on Nesterov’s Algorithm
In this section we describe and analyze a parallel algorithm for learning a γ-margin halfspace. The
algorithm of this section applies an algorithm of Nesterov (2004) that, roughly
p speaking, approximately minimizes a suitably smooth convex function to accuracy ε using O( 1/ε) iterative steps(Nesterov, 2004), each of which can be easily parallelized.
Directly applying the basic Nesterov algorithm gives us an algorithm that uses O(n) processors,
runs in parallel time O(log(n) · (1/γ)), and outputs a halfspace hypothesis that has constant accuracy. By combining the basic algorithm with random projection and boosting we get the following
stronger result:
Theorem 1 There is a parallel algorithm with the following performance guarantee: Let f , D define an unknown γ-margin halfspace over Bn . The algorithm is given as input ε, δ > 0 and access tolabeled examples (x, f (x)) that are drawn independently from D . It runs in
O(((1/γ)polylog(1/γ) + log(n)) log(1/ε)poly(log log(1/ε)) + log log(1/δ))
parallel time, usesn · poly(1/γ, 1/ε, log(1/δ))
processors, and with probability 1 − δ it outputs a hypothesis h satisfying Prx∼D [h(x) 6= f (x)] ≤ ε.
We assume that the value of γ is “known” to the algorithm, since otherwise the algorithm canuse a standard “guess and check” approach trying γ = 1, 1/2, 1/4, etc., until it finds a value thatworks.
Freund (1995) indicated how to parallelize his boosting-by-filtering algorithm. In Appendix A,
we provide a detailed proof of the following lemma.
Lemma 2 (Freund, 1995) Let D be a distribution over (unlabeled) examples. Let A be a parallel learning algorithm, and cδ and cε be absolute positive constants, such that for all D ′ withsuch issues, in order to fully establish our claimed bounds on the number of processors and the parallel running timeof our algorithms.

3077

L ONG AND S ERVEDIO

10

8

6

4

2

-4

2

-2

4

Figure 1: A plot of a loss function φ used in Section 2.
support(D ′ ) ⊆ support(D ), given draws (x, f (x)) from D ′ , with probability cδ , A outputs a hypothesis with accuracy 12 + cε (w.r.t. D ′ ) using P processors in T time. Then there is a parallel algorithm
B that, given access to independent labeled examples (x, f (x)) drawn from D , with probability
1 − δ, constructs a (1 − ε)-accurate hypothesis (w.r.t. D ) in O(T log(1/ε)poly(log log(1/ε)) +log log(1/δ)) time using poly(P , 1/ε, log(1/δ)) processors.
In Section 2.1 we describe the basic way that Nesterov’s algorithm can be used to find a halfspace hypothesis that approximately minimizes a smooth loss function over a set of γ-margin labeled
examples. (This section has nothing to do with parallelism.) Then later we explain how this algorithm is used in the larger context of a parallel algorithm for halfspaces.
2.1 The Basic Algorithm
Let S = (x1 , y1 ), . . . , (xm , ym ) be a data set of m examples labeled according to the target γ-margin
halfspace f ; that is, yi = f (xi ) for all i.
We will apply Nesterov’s algorithm to minimize a regularized loss as follows.
The loss part. For z ∈ R we definepφ(z) = 1 + z2 − z.
(See Figure 1 for a plot of φ.) For v ∈ Rn we defineΦ(v) =1 m∑ φ(yt (v · xt )).
m t=1

The regularization part. We define a regularizer
R(v) = γ2 kvk2 /100
where k · k denotes the 2-norm.
We will apply Nesterov’s iterative algorithm to minimize the following function
Ψ(v) = Φ(v) + R(v).
Let g(v) be the gradient of Ψ at v. We will use the following algorithm, due to Nesterov (2004)(see Section 2.2.1), which we call ANes . The algorithm takes a single input parameter γ > 0.
3078

PARALLEL L ARGE -M ARGIN L EARNING

Algorithm ANes :• Set µ = γ2 /50, L = 51/50.
• Initialize v0 = z0 = 0.
• For each k = 0, 1, . . . , set– vk+1 = zk − L1 g(zk ), and
√ √
L− µ

– zk+1 = vk+1 + √L+√µ (vk+1 − vk ).
We begin by establishing various bounds on Ψ that Nesterov uses in his analysis of ANes .
Lemma 3 The gradient g of Ψ has a Lipschitz constant at most 51/50.
Proof: We have∂Ψ1
= ∑ φ′ (yt (v · xt ))yt xt,i + γ2 vi /50∂vim t

and hence, writing g(v) to denote the gradient of Ψ at v, we haveg(v) =

1φ′ (yt (v · xt ))yt xt + γ2 v/50.
m∑t

Choose r ∈ Rn . Applying the triangle inequality, we have||g(v) − g(r)|| =≤≤1(φ′ (yt (v · xt )) − φ′ (yt (r · xt )))yt xt + γ2 (v − r)/50m∑t
1||(φ′ (yt (v · xt )) − φ′ (yt (r · xt )))yt xt || + γ2 ||v − r||/50m∑t
1|φ′ (yt (v · xt )) − φ′ (yt (r · xt ))| + γ2 ||v − r||/50,m∑tsince each vector xt has length at most 1. Basic calculus gives that φ′′ is always at most 1, and hence|φ′ (yt (v · xt )) − φ′ (yt (r · xt ))| ≤ |v · xt − r · xt | ≤ ||v − r||,again since xt has length at most 1. The bound then follows from the fact that γ2 ≤ 1.
We recall the definition of strong convexity (Nesterov, 2004, pp. 63–64): a multivariate function
q is µ-strongly convex if for all v, w and all α ∈ [0, 1] it holds thatq(αv + (1 − α)w) ≤ αq(v) + (1 − α)q(w) −µα(1 − α)||v − w||2.
2

(For intuition’s sake, it may be helpful to note that a suitably smooth q is µ-strongly convex if any
restriction of q to a line has second derivative that is always at least µ.) We recall the fact thatstrongly convex functions have unique minimizers.
Lemma 4 Ψ is µ-strongly convex.
3079

L ONG AND S ERVEDIO

Proof: This follows directly from the fact that µ = γ2 /50, Φ is convex, and ||v||2 is 2-strongly
convex.
Given the above, the following lemma is an immediate consequence of Theorem 2.2.3 of Nesterov’s (2004) book. The lemma upper bounds the difference between Ψ(vk ), where vk is the pointcomputed in the k-th iteration of Nesterov’s algorithm ANes , and the true minimum value of Ψ. A
proof is in Appendix B.
2

/2)
√
.
Lemma 5 Let w be the minimizer of Ψ. For each k, we have Ψ(vk ) − Ψ(w) ≤ 4L(1+µ||w||√(2 L+k µ)2

2.2 The Finite Precision Algorithm
The algorithm analyzed in the previous subsection computes real numbers with infinite precision.
Now we will analyze a finite precision variant of the algorithm, which we call ANfp (for “Nesterov
finite precision”).
(We note that d’Aspremont (2008), also analyzed a similar algorithm with an approximate gradient, but we were not able to apply his results in our setting because of differences between his
assumptions and our needs. For example, the algorithm described by d’Aspremont (2008) assumed
that optimization was performed over a compact set C, and periodically projected solutions onto C;
it was not obvious to us how to parallelize this algorithm.)
We begin by writing the algorithm as if it took two parameters, γ and a precision parameterβ > 0. The analysis will show how to set β as a function of γ. To distinguish between ANfp and ANes
we use hats throughout our notation below.
Algorithm ANfp :• Set µ = γ2 /50, L = 51/50.
• Initialize v̂0 = ẑ0 = 0.
• For each k = 0, 1, . . . ,– Let r̂k be such that ||r̂k − L1 g(ẑk )|| ≤ β. Set– v̂k+1 = ẑk − r̂k , and

√ √
L− µ

– ẑk+1 = v̂k+1 + √L+√µ (v̂k+1 − v̂k ).
We discuss the details of exactly how this finite-precision algorithm is implemented, and theparallel running time required for such an implementation, at the end of this section.
Our analysis of this algorithm will proceed by quantifying how closely its behavior tracks thatof the infinite-precision algorithm.
Lemma 6 Let v0 , v1 , ... be the sequence of points computed by the infinite precision version of
Nesterov’s algorithm, and v̂0 , v̂1 , ... be the corresponding finite-precision sequence. Then for all k,
we have ||vk − v̂k || ≤ β · 7k .
Proof: Let ŝk = r̂k − g(ẑk ). Our proof is by induction, with the additional inductive hypothesis that||zk − ẑk || ≤ 3β · 7k .
The base case is trivially true.
3080

PARALLEL L ARGE -M ARGIN L EARNING

We have
1
1||vk+1 − v̂k+1 || = (zk − g(zk )) − (ẑk − ( g(ẑk ) + ŝk ) ,LLand, using the triangle inequality, we get1
1g(zk ) − ( g(ẑk ) + ŝk )L
L
1
1≤ 3β · 7k +g(zk ) − ( g(ẑk ) + ŝk )LL1(triangle inequality)≤ 3β · 7k + ||g(zk ) − g(ẑk )|| + ||ŝk ||L≤ 3β · 7k + ||zk − ẑk || + ||ŝk ||(by Lemma 3)||vk+1 − v̂k+1 || ≤ ||zk − ẑk || +≤ 3β · 7k + 3β · 7k + β
k+1

< β·7

(by definition of ŝk ).

Also, we have||zk+1 − ẑk+1 || =
≤

√
√
L− µ
2
p
(vk+1 − v̂k+1 ) − √√ (vk − v̂k )L+ µ
1 + µ/L
√
√
L− µ
2
√
p
(vk+1 − v̂k+1 ) +√ (vk − v̂k )L+ µ
1 + µ/L≤ 2||vk+1 − v̂k+1 || + ||vk − v̂k ||≤ 2β · 7k+1 + β · 7k
≤ 3β · 7k+1 ,completing the proof.
2.3 Application to Learning
Now we are ready to prove Theorem 1. By Lemma 2 it suffices to prove the theorem in the case inwhich ε = 7/16 and δ = 1/2.
We may also potentially reduce the number of variables by applying a random projection. We
say that a random projection matrix is a matrix A chosen uniformly from {−1, 1}n×d . Given suchan A and a√unit vector w ∈ Rn (defining a target halfspace f (x) = sign(w · x)), let w′ denote thevector (1/ d)wA ∈ Rd . After transformation by A the distribution D over Bn is transformed to a
distribution D ′ over Rd√in the natural way: a draw x′ from D ′ is obtained by making a draw x fromD and setting x′ = (1/ d)xA. We will use the following lemma, which is a slight variant of known
lemmas (Arriaga and Vempala, 2006; Blum, 2006); we prove this exact statement in Appendix C.
Lemma 7 Let f (x) = sign(w · x) and D define a γ-margin halfspace as described in the introduction. For d = O((1/γ2 ) log(1/γ)), a random n × d projection
i 99/100h ′ matrix A will with probability
w
′
′
′
′
induce D and w as described above such that Prx′ ∼D ′ kw′ k · x < γ/2 or kx k2 > 2 ≤ γ4 .
We assume without loss of generality that γ = 1/integer.
3081

L ONG AND S ERVEDIOThe algorithm first selects an n× d random projection matrix A where d = O(log(1/γ)/γ2 ). Thisdefines a transformation ΦA : Bn → Rd as follows: given x ∈ Bn , the vector ΦA (x) ∈ Rd is obtainedbyp(i) rounding each xi to the nearest integer multiple of 1/(4⌈ n/γ⌉); then(ii) setting x′ = 2√1 d xA (we scale down by an additional factor of two to get examples that arecontained in the unit ball Bd ); and finally(iii) rounding each x′i to the nearest multiple of 1/(8⌈d/γ⌉).
Given x it is easy to compute ΦA (x) using O(n log(1/γ)/γ2 ) processors in O(log(n/γ)) time. Let
D ′ denote the distribution over Rd obtained by applying ΦA to D . Across all coordinates D ′ issupported on rational numbers with the same poly(1/γ) common denominator. By Lemma 7, withprobability 99/100
h
i
′
′
′
′ def
′
Pr
x
·
(w
/kw
k)
<
γ
=
γ/8
or
kx
k
>
1
≤ γ4 .
2′′x ∼D

Our algorithm draws c0 d examples by sampling from D ′ . Applying Lemma 7, we may assume
without loss of generality that our examples have d = O(log(1/γ)/γ2 ) and that the margin γ′ after
the projection is at least Θ(γ), and that all the coordinates of all the examples have a common
denominator which is at most poly(1/γ). Thus far the algorithm has used O(log(n/γ)) parallel timeand O(n log(1/γ)/γ2 ) many processors.
Next, the algorithm applies ANfp from the previous section for K stages, where K = ⌈c1 /γ′ ⌉ and
β = c2 7−K . Here c0 , c1 , and c2 are absolute positive constants; our analysis will show that there
exist choices of these constants that give Theorem 1.
For our analysis, as before, let w be the minimizer of Ψ, and let u be a unit normal vector forthe target halfspace f (x) = sign(u · x). (We emphasize that Ψ is now defined using the projectedd-dimensional examples and with γ′ in place of γ in the definition of the regularizer R.)
Our first lemma gives an upper bound on the optimal value of the objective function.
Lemma 8 Ψ(w) ≤ 0.26.

Proof Since w is the minimizer of Ψ we have Ψ(w) ≤ Ψ(3u/γ′ ). In turn Ψ(3u/γ′ ) is easily seen to
be at most φ(3) + 9/100 ≤ 0.26, since every example has margin at least γ′ with respect to u.
Next, we bound the norm of w.
Lemma 9 ||w||2 ≤ 26/γ′2 .
Proof: The definition of Ψ gives||w||2 ≤ 100Ψ(w)/γ′2
and combining with Lemma 8 gives ||w||2 ≤ 26/γ′2 .
Now we can bound the objective function value of vK .
Lemma 10 For c1 a sufficiently large absolute constant, we have Ψ(vK ) ≤ 2/5.
3082

PARALLEL L ARGE -M ARGIN L EARNING

Proof: Plugging Lemma 9 into the RHS of Lemma 5 and simplifying, we getΨ(vK ) − Ψ(w) ≤751√.
25(2 51 + γ′ K)2

Ψ(vK ) ≤ 0.26 +

751√.
25(2 51 + γ′ K)2Applying Lemma 8, we getfrom which the lemma follows.
Now we can bound vK nearly the same way that we bounded w:
Lemma 11 ||vK || ≤ 7/γ′ .
Proof: The argument is similar to the proof of Lemma 9, using Lemma 10 in place of Lemma 8.
Now we can bound the value of the objective function of the finite precision algorithm.
Lemma 12 There exist absolute positive constants c1 , c2 such that Ψ(v̂K ) ≤ 3/7.
′

Proof Because β = c2 7−⌈c1 /γ ⌉ , Lemma 6 implies that ||v̂K − vK || ≤ c2 . Since φ has a Lipschitz
constant of 2, so does Φ, and consequently we have that
Φ(v̂K ) − Φ(vK ) ≤ 2c2 .

(1)Next, since Lemma 11 gives ||vK || ≤ 7/γ′ , and ||v̂K − vK || ≤ c2 , we have ||v̂K || ≤ 7/γ′ + c2 , which
in turn implies
kv̂K k2 − kvK k2 ≤ (7/γ′ + c2 )2 − (7/γ′ )2 = 14c2 /γ′ + c22 .
and thus

14c2 γ′ (γ′ )2 c22
+
.
100
100
Combining this with (1), we get that for c2 less than a sufficiently small positive absolute constant,
we have Ψ(v̂K ) − Ψ(vK ) < 3/7 − 2/5, and combining with Lemma 10 completes the proof.
R(v̂K ) − R(vK ) ≤Finally, we observe that Ψ(v̂k ) is an upper bound on the fraction of examples in the sample thatare misclassified by v̂k . Taking c0 sufficiently large and applying standard VC sample complexity
bounds, we have established the (ε, δ) PAC learning properties of the algorithm. (Recall from thestart of this subsection that we have taken ε = 7/16 and δ = 1/2.)
It remains to analyze the parallel time complexity of the algorithm. We have already analyzed
the parallel time complexity of the initial random projection stage, and shown that we may take thefinite-precision iterative algorithm ANfp to run for O(1/γ) stages, so it suffices to analyze the paralleltime complexity of each stage ANfp . We will show that each stage runs in parallel time polylog(1/γ)
and thus establish the theorem.
Recall that we have set β = Θ(7−K ) and that K = Θ(1/γ). The invariant we maintain throughout
each iteration k of algorithm ANfp is that each coordinate of v̂k is a poly(K)-bit rational number andeach coordinate of ẑk is a poly(K)-bit rational number. It remains to show that given such values v̂kand ẑk , in parallel time polylog(1/γ) using log(1/γ) processors,
3083

L ONG AND S ERVEDIO√
1. it is possible to compute each coordinate g(ẑk )i to accuracy 2−100K / d;2. it is possible to determine a vector r̂k such that kr̂k − g(ẑk )k ≤ β, and that each coefficient of
the new value v̂k+1 = ẑk − r̂k is again a poly(K)-bit rational number; and3. it is possible to compute the new value ẑk+1 and that each coordinate of ẑk+1 is again apoly(K)-bit rational number.
We begin by analyzing the approximate computation of the gradient. Recall thatg(v) =

1φ′ (yt (v · xt ))yt xt + γ2 v/50.
m∑t

Note thatz− 1.
1 + z2
To analyze the approximation of φ′ we will first need a lemma about approximating the squareroot function efficiently in parallel. While related statements are known and our statement below
can be proved using standard techniques, we have included a proof in Appendix D because we do
not know a reference for precisely this statement.
φ′ (z) = √Lemma 13 There is an algorithm Ar that, given an L-bit positive rational number z and an L-bit√
positive rational number β as input, outputs Ar (z) for which |Ar (z)− z| ≤ β in poly(log log(1/β),log L) parallel time using poly(log(1/β), L) processors.
Armed with the ability to approximate the square root, we can easily approximate φ′ .
Lemma 14 There is an algorithm A p that, given an L-bit positive rational number z, and an
L-bit positive rational number β ≤ 1/4, outputs A p (z) for which |A p (z) − φ′ (z)| ≤ β in at mostpoly(log log(1/β), log L) parallel time using poly(log(1/β), L) processors.
√
Proof: Assume
that β ≤ 1/4. Then, because 1 + z2 ≥ 1, if an approxi√√ without loss of generality
mation s of 1 + z2 satisfies |s − 1 + z2 | ≤ β/2L+1 , then11
≤ β/2L .
−√s
1 + z2

Applying Lemma 13 and recalling the well-known fact that there are efficient parallel algorithms
for division (see Beame et al., 1986) completes the proof.
Using this approximation for φ′ , and calculating the sums in the straightforward way, we get therequired approximation r̂k . We may assume without loss of generality that each component of r̂khas been rounded to the nearest multiple of β/2. Since each component of g has size at most 2, andthe denominator of r̂k has O(K) bits, r̂k in total requires at most O(K) bits. We can assume without√
1− µloss of generality that γ2 /50 is a perfect square, so multiplying the components of a vector by 1+√µ
can be accomplished while adding O(log(1/γ)) bits to each of their rational representations. Thus,a straightforward induction implies that each of the components of each of the denominators of vk
and zk can be written with k log(1/γ) + O(1/γ) = O((1/γ) log(1/γ)) bits.
To bound the numerators of the components of vk and zk , it suffices to bound the norms of vk
and zk . Lemma 11 implies that ||vk || ≤ 5/γ′ and so Lemma 6 implies ||v̂k || ≤ 5/γ′ + 1 which in turn
directly implies ||ẑk || ≤ 3(5/γ′ + 1).
Thus, each iteration takes O(polylog(1/γ)) time, and there are a total of O(1/γ) iterations. This
completes the proof of Theorem 1.
3084

PARALLEL L ARGE -M ARGIN L EARNING

3. Lower Bound for Parallel Boosting in the Oracle Model
Boosting is a widely used method for learning large-margin halfspaces. In this section we consider
the question of whether boosting algorithms can be efficiently parallelized. We work in the original
PAC learning setting (Valiant, 1984; Kearns and Vazirani, 1994; Schapire, 1990) in which a weaklearning algorithm is provided as an oracle that is called by the boosting algorithm, which must
simulate a distribution over labeled examples for the weak learner. Our main result for this settingis that boosting is inherently sequential; being able to call the weak learner multiple times in parallel
within a single boosting stage does not reduce the overall number of sequential boosting stages thatare required. In fact we show this in a very strong sense, by proving that a boosting algorithm thatruns arbitrarily many copies of the weak learner in parallel in each stage cannot save even one stage
over a sequential booster that runs the weak learner just once in each stage. This lower bound isunconditional and information-theoretic.
Below we first define the parallel boosting framework and give some examples of parallel boosters. We then state and prove our lower bound on the number of stages required by parallel boosters.
A consequence of our lower bound is that Ω(log(1/ε)/γ2 ) stages of parallel boosting are requiredin order to boost a γ-advantage weak learner to achieve classification accuracy 1 − ε no matter how
many copies of the weak learner are used in parallel in each stage.
3.1 Parallel Boosting
Our definition of weak learning is standard in PAC learning, except that for our discussion it suffices
to consider a single target function f : X → {−1, 1} over a domain X .
Definition 15 A γ-advantage weak learner L is an algorithm that is given access to a source of independent random labeled examples drawn from an (unknown and arbitrary) probability distribution
P over labeled examples {(x, f (x))}x∈X . L must2 return a weak hypothesis h : X → {−1, 1} thatsatisfies Pr(x, f (x))←P [h(x) = f (x)] ≥ 1/2 + γ. Such an h is said to have advantage γ w.r.t. P .
We fix P to henceforth denote the initial distribution over labeled examples; that is, P is a distribution over {(x, f (x))}x∈X where the marginal distribution PX may be an arbitrary distribution over
X.
Intuitively, a boosting algorithm runs the weak learner repeatedly on a sequence of carefully
chosen distributions P1 , P2 , . . . to obtain weak hypotheses h1 , h2 , . . . , and combines the weak hypotheses to obtain a final hypothesis h that has high accuracy under P . We first give a definition that
captures the idea of a “sequential” (non-parallel) booster, and then extend the definition to parallel
boosters.
3.1.1 S EQUENTIAL B OOSTERS
We give some intuition to motivate our definition. In a normal (sequential) boosting algorithm,
the probability weight that the (t + 1)st distribution Pt+1 puts on a labeled example (x, f (x)) may
depend on the values of all the previous weak hypotheses h1 (x), . . . , ht (x) and on the value of f (x).
No other dependence on x is allowed, since intuitively the only interface that the boosting algorithm
should have with each data point is through its label and the values of the weak hypotheses. We
2. The usual definition of a weak learner would allow L to fail with probability δ. This probability can be made exponentially small by running L multiple times so for simplicity we assume there is no failure probability.

3085

L ONG AND S ERVEDIO

further observe that since the distribution P is the only source of labeled examples, a booster should
construct the distribution Pt+1 by somehow “filtering” examples drawn from P based on the values
h1 (x), . . . , ht (x), f (x). We thus define a sequential booster as follows:
Definition 16 (Sequential booster) A T -stage sequential boosting algorithm is defined by a sequence α1 , . . . , αT of functions αt : {−1, 1}t → [0, 1] and a (randomized) Boolean function h :{−1, 1}T → {−1, 1}. In the t-th stage of boosting, the distribution Pt over labeled examples that isgiven to the weak learner by the booster is obtained from P by doing rejection sampling according
to αt . More precisely, a draw from Pt is made as follows: draw (x, f (x)) from P and compute thevalue px := αt (h1 (x), . . . , ht−1 (x), f (x)). With probability px accept (x, f (x)) as the output of thedraw from Pt , and with the remaining 1 − px probability reject this (x, f (x)) and try again. In stage
t the booster gives the weak learner access to Pt as defined above, and the weak learner generates
a hypothesis ht that has advantage at least γ w.r.t. Pt . Together with h1 , . . . , ht−1 , this ht enables thebooster to give the weak learner access to Pt+1 in the next stage.
After T stages, weak hypotheses h1 , . . . , hT have been obtained from the weak learner. The final
hypothesis of the booster is H(x) := h(h1 (x), . . . , hT (x)), and its accuracy isminPrh1 ,...,hT (x, f (x))←P[H(x) = f (x)],where the min is taken over all sequences h1 , . . . , hT of T weak hypotheses subject to the condition
that each ht has advantage at least γ w.r.t. Pt .
Many PAC-model boosting algorithms in the literature are covered by Definition 16, such as
the original boosting algorithm of Schapire (1990), Boost-by-Majority (Freund, 1995), MadaBoost(Domingo and Watanabe, 2000), BrownBoost (Freund, 2001), SmoothBoost (Servedio, 2003), FilterBoost (Bradley and Schapire, 2007) and others. All these boosters use Ω(log(1/ε)/γ2 ) stagesof boosting to achieve 1 − ε accuracy, and indeed Freund (1995) has shown that any sequential
booster must run for Ω(log(1/ε)/γ2 ) stages. More precisely, Freund (1995) modeled the phenomenon of boosting using the majority function to combine weak hypotheses as an interactive
game between a “weightor” and a “chooser” (see Freund, 1995, Section 2). He gave a strategy for
the weightor, which corresponds to a boosting algorithm, and showed that after T stages of boosting this boosting algorithm generates a final hypothesis that is guaranteed to have error at mostj
def ⌊T /2⌋
vote(γ, T ) = ∑ j=0 Tj 12 + γ (1/2 − γ)T − j (see Freund, 1995, Theorem 2.1). Freund also gives
a matching lower bound by showing (see his Theorem 2.4) that any T -stage sequential booster musthave error at least as large as vote(γ, T ), and so consequently any sequential booster that generates
a (1 − ε)-accurate final hypothesis must run for Ω(log(1/ε)/γ2 ) stages. Our Theorem 18 below
extends this lower bound to parallel boosters.
3.1.2 PARALLEL B OOSTING
Parallel boosting is a natural generalization of sequential boosting. In stage t of a parallel booster theboosting algorithm may simultaneously run the weak learner many times in parallel using different
probability distributions. The distributions that are used in stage t may depend on any of the weak
hypotheses from earlier stages, but may not depend on any of the weak hypotheses generated byany of the calls to the weak learner in stage t.
3086

PARALLEL L ARGE -M ARGIN L EARNING

Definition 17 (Parallel booster) A T -stage parallel boosting algorithm with N-fold parallelism
is defined by T N functions {αt,k }t∈[T ],k∈[N] and a (randomized) Boolean function h, where αt,k :{−1, 1}(t−1)N+1 → [0, 1] and h : {−1, 1}T N → {−1, 1}. In the t-th stage of boosting the weak learneris run N times in parallel. For each k ∈ [N], the distribution Pt,k over labeled examples that is given
to the k-th run of the weak learner is as follows: a draw from Pt,k is made by drawing a labeled example (x, f (x)) from P , computing the value px := αt,k (h1,1 (x), . . . , ht−1,N (x), f (x)), and accepting(x, f (x)) as the output of the draw from Pt,k with probability px (and rejecting it and trying again
otherwise). In stage t, for each k ∈ [N] the booster gives the weak learner access to Pt,k as defined
above and the weak learner generates a hypothesis ht,k that has advantage at least γ w.r.t. Pt,k .
Together with the weak hypotheses {hs, j }s∈[t−1], j∈[N] obtained in earlier stages, these ht,k ’s enable
the booster to give the weak learner access to each Pt+1,k in the next stage.
After T stages, T N weak hypotheses {ht,k }t∈[T ],k∈[N] have been obtained from the weak learner.
The final hypothesis of the booster is H(x) := h(h1,1 (x), . . . , hT,N (x)), and its accuracy isminPrht,k (x, f (x))←P[H(x) = f (x)],where the min is taken over all sequences of T N weak hypotheses subject to the condition that eachht,k has advantage at least γ w.r.t. Pt,k .
The parameter N above corresponds to the number of processors that the parallel booster isusing. Parallel boosting algorithms that call the weak learner different numbers of times at different
stages fit into our definition simply by taking N to be the max number of parallel calls made atany stage. Several parallel boosting algorithms have been given in the literature; in particular,
all boosters that construct branching program or decision tree hypotheses are of this type. The
number of stages of these boosting algorithms corresponds to the depth of the branching programor decision tree that is constructed, and the number of nodes at each depth corresponds to theparallelism parameter. Branching program boosters (Mansour and McAllester, 2002; Kalai andServedio, 2005; Long and Servedio, 2005, 2008) all make poly(1/γ) many calls to the weak learnerwithin each stage and all require Ω(log(1/ε)/γ2 ) stages, while the earlier decision tree booster
2(Kearns and Mansour, 1996) requires Ω(log(1/ε)/γ2 ) stages but makes 2Ω(log(1/ε)/γ ) parallel calls
to the weak learner in some stages. Our results in the next subsection will imply that any parallel
booster must run for Ω(log(1/ε)/γ2 ) stages no matter how many parallel calls to the weak learnerare made in each stage.
3.2 The Lower Bound and Its Proof
Our lower bound theorem for parallel boosting is the following:
Theorem 18 Let B be any T -stage parallel boosting algorithm with N-fold parallelism. Then for
any 0 < γ < 1/2, when B is used to boost a γ-advantage weak learner the resulting final hypothesis
may have error as large as vote(γ, T ) (see the discussion after Definition 17).
We emphasize that Theorem 18 holds for any γ and any N that may depend on γ in an arbitraryway.
The theorem is proved as follows: fix any 0 < γ < 1/2 and fix B to be any T -stage parallel
boosting algorithm. We will exhibit a target function f and a distribution P over {(x, f (x))x∈X , and3087

L ONG AND S ERVEDIO

describe a strategy that a weak learner W can use to generate weak hypotheses ht,k that all haveadvantage at least γ with respect to the distributions Pt,k . We show that with this weak learner W ,the resulting final hypothesis H that B outputs will have accuracy at most 1 − vote(γ, T ).
We begin by describing the desired f and P , both of which are fairly simple. The domain X
of f is X = Z × Ω, where Z denotes the set {−1, 1} and Ω denotes the set of all infinite sequencesω = (ω1 , ω2 , . . . ) where each ωi belongs to {−1, 1}. The target function f is simply f (z, ω) = z; thatis, f always simply outputs the first coordinate of its input vector. The distribution P = (P X , P Y )over labeled examples {(x, f (x))}x∈X is defined as follows.3 A draw from P is obtained by drawing
x = (z, ω) from P X and returning (x, f (x)). A draw of x = (z, ω) from P X is obtained by firstchoosing a uniform random value in {−1, 1} for z, and then choosing ωi ∈ {−1, 1} to equal z
with probability 1/2 + γ independently for each i. Note that under P , given the label z = f (x) of alabeled example (x, f (x)), each coordinate ωi of x is correct in predicting the value of f (x, z) withprobability 1/2 + γ independently of all other ω j ’s.
We next describe a way that a weak learner W can generate a γ-advantage weak hypothesis eachtime it is invoked by B. Fix any t ∈ [T ] and any k ∈ [N], and recall that Pt,k is the distribution overlabeled examples that is used for the k-th call to the weak learner in stage t. When W is invokedwith Pt,k it replies as follows (recall that for x ∈ X we have x = (z, ω) as described above):(i) If Pr(x, f (x))←Pt,k [ωt = f (x)] ≥ 1/2 + γ then the weak hypothesis ht,k (x) is the function “ωt ,”the (t + 1)-st coordinate of x. Otherwise,(ii) the weak hypothesis ht,k (x) is “z,” the first coordinate of x. (Note that since f (x) = z for all x,
this weak hypothesis has zero error.)
It is clear that each weak hypothesis ht,k generated as described above indeed has advantage atleast γ w.r.t. Pt,k , so the above is a legitimate strategy for W . It is also clear that if the weak learner
ever uses option (ii) above at some invocation (t, k) then B may output a zero-error final hypothesis
simply by taking H = ht,k = f (x). On the other hand, the following crucial lemma shows that if
the weak learner never uses option (ii) for any (t, k) then the accuracy of B is upper bounded byvote(γ, T ):Lemma 19 If W never uses option (ii) then Pr(x, f (x))←P [H(x) 6= f (x)] ≥ vote(γ, T ).
Proof If the weak learner never uses option (ii) then H depends only on variables
ω1 , . . . , ωTand hence is a (randomized) Boolean function over these variables. Recall that for (x = (z, ω),f (x) = z) drawn from P , each coordinate
ω1 , . . . , ωT
independently equals z with probability 1/2 + γ. Hence the optimal (randomized) Boolean function
H over inputs ω1 , . . . , ωT that maximizes the accuracy Pr(x, f (x))←P [H(x) = f (x)] is the (deterministic) function H(x) = Maj(ω1 , . . . , ωT ) that outputs the majority vote of its input bits. (This can be
3. Note that P X and P Y are not independent; indeed, in a draw (x, y = f (x)) from (P X , P Y ) the outcome of x completely
determines y.

3088

PARALLEL L ARGE -M ARGIN L EARNING

easily verified using Bayes’ rule in the usual “Naive Bayes” calculation.) The error rate of this H is
precisely the probability that at most ⌊T /2⌋ “heads” are obtained in T independent (1/2 + γ)-biased
coin tosses, which equals vote(γ, T ).
Thus to prove Theorem 18 it suffices to prove the following lemma, which we prove by induction
on t:
Lemma 20 W never uses option (ii) (that is, Pr(x, f (x))←Pt,k [ωt = f (x)] ≥ 1/2 + γ always).
Proof Base case (t = 1). For any k ∈ [N], since t = 1 there are no weak hypotheses from previous
stages, so the value of the rejection sampling parameter px is determined by the bit f (x) = z (seeDefinition 17). Hence P1,k is a convex combination of two distributions which we call D1 andD−1. For b ∈ {−1, 1}, a draw of (x = (z, ω); f (x) = z) from Db is obtained by setting z = b andindependently setting each coordinate ωi equal to z with probability 1/2 + γ. Thus in the convex
combination P1,k of D1 and D−1 , we also have that ω1 equals z (that is, f (x)) with probability
1/2 + γ. So the base case is done.
Inductive step (t > 1). Thanks to the conditional independence of different coordinates ωi given
the value of z in a draw from P , the proof is quite similar to the base case.
Fix any k ∈ [N]. The inductive hypothesis and the weak learner’s strategy together imply thatfor each labeled example (x = (z, ω), f (x) = z), since hs,ℓ (x) = ωs for s < t, the rejection sampling
parameter px = αt,k (h1,1 (x), . . . , ht−1,N (x), f (x)) is determined by ω1 , . . . , ωt−1 and z and does notdepend on ωt , ωt+1 , .... Consequently the distribution Pt,k over labeled examples is some convex
combination of 2t distributions which we denote Db , where b ranges over {−1, 1}t corresponding
to conditioning on all possible values for ω1 , . . . , ωt−1 , z. For each b = (b1 , . . . , bt ) ∈ {−1, 1}t , a drawof (x = (z, ω); f (x) = z) from Db is obtained by setting z = bt , setting (ω1 , . . . , ωt−1 ) = (b1 , . . . , bt−1 ),and independently setting each other coordinate ω j ( j ≥ t) equal to z with probability 1/2+γ. In particular, because ωt is conditionally independent of ω1 , ..., ωt−1 given z, Pr(ωt = z|ω1 = b1 , ..., ωt−1 =bt−1 ) = Pr(ωt = z) = 1/2 + γ. Thus in the convex combination Pt,k of the different Db ’s, we also
have that ωt equals z (that is, f (x)) with probability 1/2 + γ. This concludes the proof of the lemma
and the proof of Theorem 18.

4. Conclusion
There are many natural directions for future work on understanding the parallel complexity of learning large-margin halfspaces. One natural goal, of course, is to give an algorithm that provides anaffirmative answer to the main question. But it is not clear to us that such an algorithm must actuallyexist, and so another intriguing direction is to prove negative results giving evidence that parallel
learning of large-margin halfspaces is computationally hard.
As one example of a possible negative result, perhaps it is the case that (assuming P 6= NC)
there is no poly(n)-processor, polylog(n)-time algorithm with the following performance guarantee: given a sample of poly(n) many n-dimensional labeled examples that are consistent with some1/poly(n)-margin halfspace, the algorithm outputs a consistent halfspace hypothesis. A stronger
result would be that no such algorithm can even output a halfspace hypothesis which is consistent3089

L ONG AND S ERVEDIO

with 99% (or 51%) of the labeled examples. Because of the requirement of a halfspace representation for the hypothesis such results would not directly contradict the main question, but they arecontrary to it in spirit. We view the possibility of establishing such negative results as an interesting
direction worthy of future study.

Acknowledgments
We thank Sasha Rakhlin for telling us about the paper of Soheili and Peña (2012), and anonymous
reviewers for helpful comments.

Appendix A. Proof of Lemma 2
First, let us establish that we can “boost the confidence” efficiently. Suppose we have an algorithm
that achieves accuracy 1 − ε in parallel time T ′′ with probability cδ . Then we can run O(log(1/δ))
copies of this algorithm in parallel, then test each of their hypotheses in parallel using O(log(1/δ)/ε)examples. The tests of individual examples can be done in parallel, and we can compute each
empirical error rate in O(log(1/ε) + log log(1/δ)) time. Then we can output the hypothesis with thebest accuracy on this additional test data. Finding the best hypothesis takes at most O(log log(1/δ))
parallel time (with polynomially many processors). The total parallel time taken is then O(T ′′ +log(1/ε) + log log(1/δ)).
So now, we have as a subproblem the problem of achieving accuracy 1 − ε with constant probability, say 1/2.
The theorem statement assumes that we have as a subroutine an algorithm A that achieves constant accuracy with constant probability in time T . Using the above reduction, we can use A to getan algorithm A′ that achieves constant accuracy with probability 1 − c/ log(1/ε) (for a constant c)
in T ′ = O(T + log log log(1/ε)) time. We will use such an algorithm A′ . (Note that the time taken
by A′ is an upper bound on the number of examples needed by A′ .)Algorithm B runs a parallel version of a slight variant of the “boosting-by-filtering” algorithm
due to Freund (1995), using A′ as a weak learner. Algorithm B uses parameters α and T :• For rounds t = 0, ..., T − 12– draw m = 2Tε α max{T ′ , 4 ln 32Tε α } examples, call them
St = {(xt,1 , yt,1 ), ..., (xt,m , yt,m )}.
– for each i = 1, ..., m,∗ let rt,i be the the number of previous base classifiers h0 ,...,ht−1 that are correct on(xt,i , yt,i ), and 1TT( 2 + α)⌊ 2 ⌋−rt,i ( 12 − α)⌈ 2 ⌉−t−1+rt,i ,∗ wt,i = ⌊TT−t−1
2 ⌋−rt,i 1
TT– let wt,max = maxr ⌊T −t−1
( 2 + α)⌊ 2 ⌋−r ( 21 − α)⌈ 2 ⌉−t−1+r be the largest possible valueT
2 ⌋−rthat any wt,i could take,– apply the rejection method as follows: for each i ∈ St ,∗ choose ut,i uniformly from [0, 1],

3090

PARALLEL L ARGE -M ARGIN L EARNING

wt,i, set at,i = 1∗ if ut,i ≤ wt,max– if there is a j such that j >T αwt,max
max
ε

n

j

∑i=1 at,i , 4 ln

16T 2 αwt,maxε(1−ε)o∗ output a hypothesis ht that predicts randomly,∗ otherwise, pass the examples in St to Algorithm A′ , which returns ht .
• Output the classifier obtained by taking a majority vote over h0 , ..., hT −1 .
The only difference between algorithm B, as described above, and the way the algorithm is
described by Freund (1995) is that, in the above description, a batch of examples is chosen at the
beginning of the round. The number of examples is set using Freund’s upper bound on the numberof examples that can be chosen in a given round (see the displayed equation of the boost-by-majority
paper (Freund, 1995) immediately before (18)). In Freund’s description of this algorithm, once thecondition which causes the algorithm to output a random hypothesis is reached, the algorithm stops
sampling, but, for a parallel version, it is convenient to sample all of the examples for a round inparallel.
Freund (1995) proves that, if α is a constant depending only on the accuracy of the hypotheses
output by A′ , then T = O(log(1/ε)) suffices for algorithm B to output a hypothesis with accuracy
1 − ε with probability 1/2. So the parallel time taken is O(log(1/ε)) times the time taken in each
iteration.
Let us now consider the time taken in each iteration. The weights for the various examples canbe computed in parallel. The value of wt,i is a product of O(T ) quantities, each of which can be
expressed using T bits, and can therefore be computed in O(poly(log T )) = O(poly(log log(1/ε)))parallel time, as can wt,max . The rejection step also may be done in O(poly(log log(1/ε))) time inparallel for each example. To check whether there is a j such that)(j
16T 2 αwt,max
T αwt,max,max ∑ at,i , 4 lnj>εε(1 − ε)i=1
jAlgorithm B can compute the prefix sums ∑i=1 at,i , and then test them in parallel. The prefix sums
can be computed in log(T ) parallel rounds (each on log(T )-bit numbers), using the standard technique of placing the values of at,i on the leaves of a binary tree, and working up from the leaves tothe root, computing the sums of subtrees, then making a pass down the tree, passing each node’s
sum to its right child, and using these to compute prefix sums in the obvious way.

Appendix B. Proof of Lemma 5
Algorithm ANes is a special case of the algorithm of (2.2.11) on page 81 of the book by Nesterov(2004), obtained by setting y0 ← 0 and x0 ← 0. The bound of Lemma 5 is a consequence of Theorem
2.2.3 on page 80 of Nesterov’s book. This Theorem applies to all functions f that are µ-strongly
convex, and continuously differentiable with a gradient that is L-Lipschitz (see pages 71, 63 and20). Lemmas 3 and 4 of this paper imply that Theorem 2.2.3 of Nesterov’s book applies to Ψ.
Plugging directly into Theorem 2.2.3 (in the special case of (2.2.11))
Ψ(vk ) − Ψ(w) ≤4L
2√√ (Ψ(0) − Ψ(w) + µ||w|| )(2 L + k µ)2

which implies the Lemma 5, since Ψ(0) ≤ 1 and Ψ(w) ≥ 0.
3091

L ONG AND S ERVEDIO

Appendix C. Proof of Lemma 7
First, we provePr[ ′Pr ′ ||x′ || > 2 > γ4 /2] < 1/200.
A x ∼D(2)

Recall that we sample x′ from√D′ by first sampling x from a distribution D over Bn (so that||x|| = 1), and then setting x′ = (1/ d)xA, so that (2) is equivalent toh√ iPr[ Pr ||xA|| > 2 d > γ4 /2] < 1/200.
A x∼D

Corollary 1 of the paper of Arriaga and Vempala (2006) directly implies that, for any x in Bn , wehave√dPr[||xA|| ≥ 2 d] ≤ 2e− 32 ,
A

so

√
d
Ex∈D [Pr[||xA|| ≥ 2 d]] ≤ 2e− 32 ,A

which implies√d
EA [ Pr [||xA|| ≥ 2 d]] ≤ 2e− 32 .
x∈DApplying Markov’s inequality,√d
Pr[ Pr [||xA|| ≥ 2 d] > 400e− 32 ] ≤ 1/200.
A x∈D

Setting d = O(log(1/γ)) then suffices to establish (2).
Now, we want to show that d = O((1/γ2 ) log(1/γ)) suffices to ensure that




w′
4
′
· x < γ/2 > γ /2 ≤ 1/200.
Pr ′Pr ′A x ∼Dkw′ k
As above, Corollary 1 of the paper by Arriaga and Vempala (2006) directly implies that there isan absolute constant c1 > 0 such that√
Pr[||w′ || = ||(1/ d)wA|| > 3/2] ≤ 2e−c1 d .
AFurthermore, for any x ∈ Bn , Corollary 2 of the paper by Arriaga and Vempala (2006) directly
implies that there is an absolute constant c2 > 0 such that2

Pr[w′ · x′ ≤ 3γ/4] ≤ 4e−c2 γ d .
A

Thus,


2
w′
′
· x ≤ γ/2 ≤ 2e−c1 d + 4e−c2 γ d .
Pr′A ||w ||


Arguing as above, we have
  ′

w
2
′
Ex∈D Pr· x ≤ γ/2 ≤ 2e−c1 d + 4e−c2 γ d ,A ||w′ ||
  ′

w
2
′
EA Pr
· x ≤ γ/2 ≤ 2e−c1 d + 4e−c2 γ d ,′x∈D ||w ||


  ′
w
′
−c1 d
−c2 γ2 d· x ≤ γ/2 > 200(2e+ 4e) ≤ 1/200,
Pr Pr
A x∈D ||w′ ||3092

PARALLEL L ARGE -M ARGIN L EARNING

from which d = O((1/γ2 ) log(1/γ)) suffices to get
  ′


w
′
4
Pr Pr
· x ≤ γ/2 > γ /2 ≤ 1/200,
A x∈D ||w′ ||completing the proof.

Appendix D. Proof of Lemma 13
First, Ar finds a rough guess u1 such that√z/2 ≤ u1 ≤

√

z.

(3)

This can be done by checking in parallel, for each of θ ∈ {1/2L , 1/2L−1 , ..., 1/2, 1, 2, ..., 2L }, whether√z ≥ θ, and outputting the largest such θ. This first step takes O(log L) time using O(L) processors.
Then, using u1 as the initial solution, Ar runs Newton’s method to find a root of the function fdefined by f (u) = u2 − z, repeatedly


z
1
.
(4)
uk+1 =uk +2
uk
As we will see below, this is done for k = 1, . . . , O(log L + log log(1/β)). Using the fact that theinitial value u1 is an L-bit rational number, a straightforward analysis using (4) shows that for allk ≤ O(log L + log log(1/β)) the number uk is a rational number with poly(L, log(1/β)) bits (if bk
is the number of bits required to represent uk , then bk+1 ≤ 2bk + O(L)). Standard results on theparallel complexity of integer multiplication thus imply that for k ≤ O(log L + log log(1/β)) theexact value of uk can be computed in the parallel time and processor bounds claimed by the Lemma.
To prove the Lemma, then, it suffices to show that taking k = O(log L + log log(1/β)) gives thedesired accuracy; we do this next.
The Newton iterates defined by (4) satisfy√ √
uk − z 2
uk+1 − z√ =√uk+1 + z
uk + z(see Weisstein, 2011), which, using induction, gives√√ kuk+1 − z
u1 − z 2.
√ =√uk+1 + z
u1 + zSolving for uk+1 yields √ 2k  √ 2k 
u1 − zu1 − z
√
√
1
+
2
√ 
u1 + zu1 + z √ uk+1 = z  √ 2k  = z 1 +
 √ 2k  .
u − z
u − z
1 − u11 +√z
1 − u11 +√z


Thus,

√  u1 −√z 2k2
z u1 +√z√
uk+1 − z = √ 2ku − z
1 − u11 +√z
3093

L ONG AND S ERVEDIO√
and, therefore, to get |uk+1 − z| ≤ β, we only need




√ k
u1 − z 2β≤ min √ , 1/2 .
√u1 + z
4 z

Applying (3),β(1/4) ≤ min √ , 1/2
4 z


2k

also suffices, and, solving for k, this means that
O(log log z + log log(1/β)) = O(log L + log log(1/β))
iterations are enough.

References
N. Alon and N. Megiddo. Parallel linear programming in fixed dimension almost surely in constanttime. J. ACM, 41(2):422–434, 1994.
R. I. Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random
projection. Machine Learning, 63(2):161–182, 2006.
P. Beame, S.A. Cook, and H.J. Hoover. Log depth circuits for division and related problems. SIAM
J. on Computing, 15(4):994–1003, 1986.
H. Block. The Perceptron: A model for brain functioning. Reviews of Modern Physics, 34:123–135,
1962.
A. Blum. Random Projection, Margins, Kernels, and Feature-Selection. In Subspace, Latent Structure and Feature Selection, pages 52–68, 2006.
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the VapnikChervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989.
J. Bradley, A. Kyrola, D. Bickson, and C. Guestrin. Parallel coordinate descent for l1-regularized
loss minimization. In Proc. 28th ICML, pages 321–328, 2011.
J. K. Bradley and R. E. Schapire. Filterboost: Regression and classification on large datasets. In
Proc. 21st NIPS, 2007.
N. Bshouty, S. Goldman, and H.D. Mathias. Noise-tolerant parallel learning of geometric concepts.
Inf. and Comput., 147(1):89–110, 1998. ISSN 0890-5401. doi: DOI: 10.1006/inco.1998.2737.
M. Collins, R. E. Schapire, and Y. Singer. Logistic regression, adaboost and bregman distances.
Machine Learning, 48(1-3):253–285, 2002.
A. d’Aspremont. Smooth optimization with approximate gradient. SIAM Journal on Optimization,
19 (3): 1171–1183, 2008.
3094

PARALLEL L ARGE -M ARGIN L EARNING

O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao. Optimal distributed online prediction. In
Proc. 28th ICML, pages 713–720, 2011.
C. Domingo and O. Watanabe. MadaBoost: A modified version of AdaBoost. In Proc. 13th COLT,
pages 180–189, 2000.
Y. Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121 (2):
256–285, 1995.
Y. Freund. An adaptive version of the boost-by-majority algorithm. Machine Learning, 43(3):293–
318, 2001.
Y. Freund and R. E. Schapire. Large margin classification using the perceptron algorithm. Machine
Learning, 37(3):277–296, 1999.
R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Limits to Parallel Computation: P-Completeness
Theory. Oxford University Press, New York, 1995.
A. Kalai and R. Servedio. Boosting in the presence of noise. Journal of Computer & System
Sciences, 71(3):266–290, 2005.
N. Karmarkar. A new polynomial time algorithm for linear programming. Combinat., 4:373–395,
1984.
M. Kearns and Y. Mansour. On the boosting ability of top-down decision tree learning algorithms.
In Proc. 28th STOC, pages 459–468, 1996.
M. Kearns and U. Vazirani. An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA, 1994.
N. Littlestone. From online to batch learning. In Proc. 2nd COLT, pages 269–284, 1989.
P. Long and R. Servedio. Martingale boosting. In Proc. 18th COLT, pages 79–94, 2005.
P. Long and R. Servedio. Adaptive martingale boosting. In Proc. 22nd NIPS, pages 977–984, 2008.
P. Long and R. Servedio. Algorithms and hardness results for parallel large margin learning. In
Proc. 25th NIPS, 2011.
Y. Mansour and D. McAllester. Boosting using branching programs. Journal of Computer & System
Sciences, 64(1):103–112, 2002.
Y. Nesterov. Introductory lectures on Convex Optimization. Kluwer, 2004.
Y. Nesterov. Excessive gap technique in nonsmooth convex minimization. SIAM J. Optimization,
16(1):235–249, 2005.
A. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata, volume XII, pages 615–622, 1962.
F. Rosenblatt. The Perceptron: a probabilistic model for information storage and organization in thebrain. Psychological Review, 65:386–407, 1958.
3095

L ONG AND S ERVEDIO

R. Schapire. The strength of weak learnability. Machine Learning, 5(2):197–227, 1990.
R. Servedio. Smooth boosting and learning with malicious noise. JMLR, 4:633–648, 2003.
S. Shalev-Shwartz and Y. Singer. On the equivalence of weak learnability and linear separability:
New relaxations and efficient boosting algorithms. Machine Learning, 80(2):141–163, 2010.
N. Soheili and J. Peña. A smooth perceptron algorithm. SIAM J. Optimization, 22(2):728–737,
2012.
L. Valiant. A theory of the learnable. Communications of the ACM, 27 (11): 1134–1142, 1984.
V. N. Vapnik and A. Y. Chervonenkis. Theory of Pattern Recognition. Nauka, 1974. In Russian.
J. S. Vitter and J. Lin. Learning in parallel. Inf. Comput., 96(2):179–202, 1992.
E. W. Weisstein. Newton’s iteration, 2011. http://mathworld.wolfram.com/NewtonsIteration.html.
DIMACS 2011 Workshop. Parallelism: A 2020 Vision. 2011.
NIPS 2009 Workshop. Large-Scale Machine Learning: Parallelism and Massive Datasets. 2009.

3096