Journal of Machine Learning Research ? (2020) ??

Submitted 9/19; Published ???

On the Complexityof Proper Distribution-Free Learningof Linear Classifiers
Philip M. Long

plong@google.com

GoogleRaphael J. Long

rafilong42@gmail.com

University of Illinois at Urbana-Champaign

Editor: Aryeh Kontorovich and Gergely Neu

Abstract
For proper distribution-free learning of linear classifiers in d dimensions from m examples,
we prove a lower bound on the optimal expected error of d−o(1)m , improving on the best√d+1
previous lower bound of d/ e−o(1), and nearly matching a m+1
upper bound achieved bymthe linear support vector machine.
Keywords: Statistical learning theory, lower bounds, linear classifiers.

1. Introduction
This paper is about the following learning problem. A learner seeks to approximate an
unknown linear classifier f in Fd = {fw,b : w ∈ Rd , b ∈ R}, where fw,b (x) = + if w · x ≥ b,
and otherwise fw,b (x) = −. For x1 , ..., xm , drawn independently at random from a probability distribution D over Rd , the learner receives examples (x1 , f (x1 )), ..., (xm , f (xm )), andoutputs h ∈ Fd . The accuracy of the learner is measured using another independent draw
xm+1 from D; its goal is to minimize the probability, with respect to all m+1 random draws
and any internal randomization, that h(xm+1 ) 6= f (xm+1 ). Let optd (m) be best possible
upper bound on this probability of error that a learner can achieve for every f and D. (Aformal definition of optd (m) can be found in Section 2.)
It is known that, for all d,√d/ e − o(1)d+1≤ optd (m) ≤
.
(1)
m
m+1
The upper bound is achieved by the linear SVM algorithm (Boser et al., 1992). (Because
we could not find a proof, we have included one in Appendix A.) The lower bound, which
also holds for learners that may output arbitrary classifiers, is implicit in the analysis of(Helmbold and Long, 2012). When d ≤ 2, a better upper bound is known: optd (m) ≤ d+o(1)m(Blumer and Littlestone, 1989; Haussler et al., 1994).
In this paper, we show that, for all d,optd (m) ≥d − o(1),m

c 2020 Philip M. Long and Raphael J. Long.
License: CC-BY 4.0, see https://creativecommons.org/licenses/by/4.0/. Attribution requirements are provided
at http://jmlr.org/papers/v?/???.html.

Long and Long

determining the leading constant for general d to within one, and matching the upper boundin the case d ≤ 2 up to the leading constant.
We use ideas from (Haussler et al., 1994) to reduce the problem of proving lower bounds
on optd (m) to the case where d = 1. The core of our analysis is a new lower bound on
opt1 (m).
Since (Ehrenfeucht et al., 1989), a common lower bound technique is to (a) choose f
and D randomly, (b) characterize the optimal algorithm for minimizing the probability oferror with respect to the random choice of f and D along with the random data, and (c)analyze the probability of error of this “Bayes optimal algorithm”. If we view the learning
problem as a game between the learner and Nature, then, informally, adopting this strategy
gives away the advantage that f and D can depend on the learner A, or, in game-theoretic
terms, that Nature can “move last”. It may be tempting to believe that no leverage is lostin this way, since the minimax theorem (von Neumann, 1928) may be loosely interpreted
as saying that nothing is lost by moving first.
The minimax theorem holds for all finite games, but it has long been known that it
can fail for some infinite games (Sion and Wolfe, 1957). Here is one example. Each playerchooses a member of the open interval (0, 1), and the winner is the player with the bigger
number. The player who moves second can win with an arbitrarily high probability. For
example, if Player B knows Player A’s (mixed) strategy, and always outputs a value a tiny
bit greater than the 99th percentile of A’s distribution, then Player B will win at least 99%of the time.
The halfline learning problem at the core of this paper is somewhat like this: it can be
helpful for Nature to put probability beyond the point where the learner is likely to put its
decision boundary. Our lower bound proof constructs D and f as a function of the learnerroughly in this way.
As we mentioned above, following (Haussler et al., 1994), we prove a lower bound foroptd (m) by embedding d copies of the problem of learning one-dimensional linear classifiers
into the d-dimensional problem. Using another embedding from (Haussler et al., 1994), ournew lower bound on opt1 (m) implies a 2d−o(1)lower bound for proper learning of axis-aligned
m
2d
hyper-rectangles in Rd , matching a known m+1
upper bound (Haussler et al., 1994) up to√e−o(1)
the leading constant, and improving on the 2d/ mlower bound implicit in (Helmbold
and Long, 2012).

Related work. The most closely related previous work was mentioned earlier. For
learning a class F of VC-dimension d without the constraint that the classifier comes from F ,Li et al. (2001) proved lower bounds of d−o(1)for classes that they constructed, matching themdgeneral upper bound of m+1 from (Haussler et al., 1994) up to the leading constant. Srebro
et al. (2010) and Shamir (2015) proved lower bounds on the complexity of distribution-freelinear regression, establishing the complexity of a formulation of this problem to within aconstant factor. Some less closely related lower bound work includes (Opper and Haussler,
1991; Devroye and Lugosi, 1995; Long, 1995; Antos and Lugosi, 1998).
2

Complexity of Learning Linear Classifiers

2. Preliminaries and main result
For w ∈ Rd and b ∈ R, the linear classifier fw,b : Rd → {−, +} parameterized by w and b
outputs fw,b (x) = + if and only if w · x ≥ b. Let Fd = {fw,b : w ∈ Rd , b ∈ R}.
For any d, an example is a member of Rd × {−, +}, a training set is a finite multiset ofexamples.
Informally, a learner is a randomized mapping from training sets to Fd . A more detailed
definition, which includes a measurability constraint, is given in Appendix B.
Let D be any probability distribution over Rd with respect to the Lebesgue σ-algebra.
For a learner A and f ∈ Fd , let erD,f (A, m) be the probability that, for x1 , ..., xm+1 drawn
independently at random from D, if A is given (x1 , f (x1 )), ..., (xm , f (xm )), it produces hsuch that h(xm+1 ) 6= f (xm+1 ).
Define erd (A, m) = supD,f erD,f (A, m) and optd (m) = inf A erd (A, m).
The following is our main result.
Theorem 1 For all d, optd (m) ≥ d−o(1)m .
As mentioned in the introduction, this nearly matches known upper bounds of opt1 (m) ≤d+o(1)
d+1
for d ≤ 2 and optd (m) ≤ m+1
for d > 2.
m

3. The d = 1 caseIn this section, we prove Theorem 1 in the case that d = 1.
First of all, define g
opt1 analogously to opt1 , with the additional constraint that the
support of D is finite. Then g
opt1 (m) ≤ opt1 (m), so it suffices to prove a lower bound forg
opt1 (m). We will do this. This obviates any measurability issues.
Given a learner A and a number m of examples, we will describe a probability distribution D over [0, 1] with finite support and f ∈ F1 such that erD,f (A, m) ≥ (1 − o(1))/m. Ourconstruction only uses a subset of F1 with a single parameter θ: classifiers that evaluate to+ on x iff x ≤ θ.
We define D as follows. First, Pr(x = 1) = 1 − 2√1m . The remaining probability is
distributed evenly among ` = m3 points in [0, 1). Let us call the set of these ` points
1
T = {t1 , ..., t` } where t1 < ... < t` ; each member of T thus has probability 2`√. Themiterative construction of T will be described later. For all t ∈ T, f (t) = +, and f (1) = −.
(The behavior of f outside T ∪ {1} does not matter.)
Let h be the output of A. Since h ∈ F1 , there are v, a ∈ R such that h(x) = + iff
vx ≥ a. If v = 0, then h is either the all-+ classifier or the all-− classifier. If v > 0, there
is a threshold θ̂ such that h(x) = + exactly when x ≥ θ̂, and, otherwise, there is a θ̂ suchthat h(x) = + exactly when x ≤ θ̂.
The following lemma enables us to assume without loss of generality that there is an θ̂such that h(x) = + if and only if x ≤ θ̂.
Lemma 2 For any learner B, there is a learner A such that
• A always outputs h for which there is an θ̂ such that h(x) = + if and only if x ≤ θ̂,and3

Long and Long

Figure 1: The distributions used in the proof of Theorem 1 concentrate probability on anegative example at 1, and spread probability evenly among positive examples in[0, 1) that are chosen depending on the learner A.

• for any choice of T , erD,f (A, m) ≤ erD,f (B, m).
Proof Whenever B outputs a classifier that assigns all elements of [0, 1] the same class,
A can also do this, either by choosing θ̂ = 2 or θ̂ = −1. If B outputs a classifier h thatpredicts + on [θ̃, ∞) for θ̃ ≤ 1, then A can improve it using the all-+ classifier, since all of
h’s predictions on T ∩ [0, θ) are incorrect.
For the rest of the proof, let θ̂ refer to the threshold associated with the output of A
that is guaranteed by Lemma 2.
Let E0 be the event that all examples (xj , yj ) have xj = 1, and let P0 be the probability
distribution on θ̂ obtained by conditioning Dm on E0 . Since E0 is the event that none of
the examples are members of T , if we change T , this does not effect P0 – conditioning on
E0 removes any effect of the choice of T on θ̂.
The choice of t1 depends on A as follows. The first case is where Pr(θ̂ < 1|E0 ) ≥ 1− √1m .
Since
lim Pr(θ̂ < 1 − 1/n | E0 ) = lim Pr(θ̂ < 1 | E0 ) − Pr(θ̂ ∈ [1 − 1/n, 1) | E0 )

n→∞

n→∞

= Pr(θ̂ < 1 | E0 ) − lim Pr(θ̂ ∈ [1 − 1/n, 1) | E0 )n→∞

= Pr(θ̂ < 1 | E0 )there is an n such that2
Pr(θ̂ < 1 − 1/n | E0 ) ≥ 1 − √ ;mwe choose t1 = 1 − 1/n for an arbitrary such n.
In the remaining case, where Pr(θ̂ < 1|E0 ) < 1 − √1m , we set t1 = 0.
For j ∈ {2, ..., `}, the choice of tj is similar. The distribution over θ̂ obtained byconditioning the m independent draws from D on the event Ej−1 that the greatest positive
example is tj−1 is unaffected by the choices of tj , ..., t` , because conditioning on Ej−1 removes
any effect of tj , ..., t` on the distribution over θ̂. We choose tj as follows. First, if Pr(θ̂ <1 | Ej−1 ) ≥ 1 − √1m , then, similarly to the case j = 1, we havelim Pr(θ̂ < 1 − 1/n | Ej−1 ) = Pr(θ̂ < 1 | Ej−1 )n→∞4Complexity of Learning Linear Classifiers

so there is an n such that Pr(θ̂ < 1 − 1/n | Ej−1 ) ≥ 1 − √2m we set tj = 1 − 1/n for an
arbitrary such n that also satisfies 1 − 1/n > tj−1 . If Pr(θ̂ < 1 | Ej−1 ) < 1 − √1m , then tj
is an arbitrary member of (tj−1 , 1).
Now that we have defined f and D, let us bound erD,f (A, m). If Pr(θ̂ < 1 | Ej ) ≥ 1− √1m ,let us say that A is reasonable at j. (Note that this is a property of A and T , and not the
random training and/or test data.) We havePr(h(xm+1 ) 6= ym+1 ) =`X

Pr(h(xm+1 ) 6= ym+1 ∧ Ej ).

j=0

Let us focus on a particular value of j. As a first case, suppose A is reasonable at j.
Then, given Ej , with probability at least 1 − √2m , tj+1 , and therefore tj 0 for all j 0 ≥ j + 1,
are all greater than θ̂. Thus, for j for which A is reasonable at j, we have


1
2
√ .
Pr(h(xm+1 ) 6= ym+1 | Ej ) ≥ (` − j) 1 − √m 2` m(2)

Now, suppose A is unreasonable at j. Then
1
Pr(h(xm+1 ) 6= ym+1 | Ej ) = Pr(θ̂ ≥ 1 | Ej ) 1 − √
2 m


1
1
√
> 1− √
2 m
m


2
1
√ .
> (` − j) 1 − √m 2` mConsider the event U that xm+1 is less than 1 but greater than all positive training
examples. Note that`−j
Pr(U |Ej ) = √ .
2` m√Thus, for every j, the probability of a mistake given Ej is at least 1−2/ m times Pr(U |Ej ).
√Thus, overall, the probability of a mistake is at least 1−2/ m times Pr(U ). Thus, it suffices
to bound Pr(U ) from below.
We bound Pr(U ) by conditioning on the very likely event E that there is at least one
positive example and that no positive example is seen twice. Conditioned on E, any orderingof the m+1 examples is equally likely (because we have conditioned a permutation-invariant
distribution on a permutation-invariant event). Given E, U holds if xm+1 is the greatest
1of the random permutations of thepositive example, which happens for a fraction m+1
data.
Finally, we claim that Pr(E) = 1 − o(1). The probability that at least one x1 , ..., xm+1
is labeled + is at least√
1 − (1 − 1/(2 m))m+1 = 1 − o(1).
The probability that any positive example is seen twice is at most ` times the probability
that any particular t ∈ T is seen twice. The latter probability is at most m2 times the5Long and Long

Figure 2: Haussler et al. (1994) proved lower bounds for linear classifiers in d dimensions
by embedding d interval-learning problems.

probability that any particular pair of examples share x values of t, which is at most 1/`2 .
Therefore the probability that any positive example is seen twice is at most `m2 /`2 =1/m = o(1), so the probability that no examples are seen twice is 1 − o(1).
Thus, overall, Pr(U ) ≥ (1 − o(1))/m, which, as argued earlier, yields Pr(h(xm+1 ) 6=
ym+1 ) ≥ (1 − o(1))/m.

4. The d > 1 case
As mentioned before, the extension to the d > 1 case uses ideas from (Haussler et al., 1994;
Li et al., 2001).
First, we note that opt(F1 , m) is a non-increasing function of m — if additional examples
hurt the learner, it could be improved by ignoring the harmful examples.
Suppose D is some distribution supported on {cei : i ∈ {1, ..., d}, c ∈ [1, 2]}, where ei
is the ith natural basis vector. Any linear classifier fw,b restricted to the support of D
can be decomposed into d pieces that are applied to Xi = {cei : c ∈ [1, 2]} for different
choices of i (see Figure 2). For each piece, the restriction of fw,b to Xi is isomorphic toa one-dimensional classifier on the interval [0, 1]. Thus, any learner A from Fd produces dlearners A1 , ..., Ad for the class of restrictions of the members of F1 to [0, 1]. (In particular,
the hypothesis of A1 , ..., Ad are linear classifiers.)
Suppose we put negative examples on each of {2ei : i ∈ {1, ..., d}}, and, if Ti is the
support set associated with Ai , put positive examples on {1 + tei : i ∈ {1, ..., d}, t ∈Ti }. This data is collectively linearly separable. We may therefore apply our construction
from Section 3 independently to each piece, viewing examples from the other pieces as
6Complexity of Learning Linear Classifiers

randomization. If h1 , ..., hd are the classifiers produced by A1 , ..., Ad , we havedPr(h(xm+1 ) 6= ym+1 ) =1X
Pr(hi (xm+1 ) 6= ym+1 | ym+1 ∈ Xi ).
di=1

Thus, it suffices to prove a lower bound for Pr(hi (xm+1 ) 6= ym+1 | ym+1 ∈ Xi ). Applying astandard Hoeffding√ bound, with probability 1 − o(1), the number of examples falling in Xi
is at most m/d + m ln m. Applying our lower bound construction from the case d = 1, weget
1 − o(1)d − o(1)√Pr(h(xm+1 ) 6= ym+1 | ym+1 ∈ Xi ) ≥=.
m
m/d + m ln m

Acknowledgments
We thank Peter Bartlett for a valuable conversation, and the reviewers for helpful comments.

Appendix A. Upper bound proof
d+1
for the linear SVM algorithm in Rd . The linear
This is a proof of an upper bound of m+1
SVM algorithm behaves as follows. When all training examples are the same class, thealgorithm outputs that class. Otherwise, it predicts using the linear classifier that separates
the positive examples from the negative examples while maximizing the distance from theclosest example to its separating hyperplane.
Suppose the training and test examples are(x1 , y1 ), ..., (xm+1 , ym+1 ),where y1 , ..., ym+1 ∈ {−1, 1}. Since any permutation of these m + 1 examples is equally
likely, it suffices to bound from above the probability of a mistake when a uniform random
choice of these m + 1 examples is the test example.
It is known (see (Cristianini et al., 2000)), that the parameters (w∗ , b∗ ) of the linear
SVM applied to all of the data (both training and test) are the solution to the problem ofchoosing w and b to minimize ||w||2 subject to∀t, yt (w · xt − b) ≥ 1.
It also is known that there are non-negative α1 , ..., αm+1 such thatP
• w∗ = m+1t=1 αt yt xt , and
Pm+1•
t=1 αt yt = 0.
Finally, the maximum-margin hyperplane is unique. If w0 = (w1∗ , ..., wd∗ , 0), and, for eachxt = (xt,1 , ..., xt,d ), we define x0t = (xt,1 , ..., xt,d , 1), the above two conditions can be consolidated into
m+1
X
w0 =
αt yt x0t .
t=1

7

Long and Long

By Carathéodory’s Theorem for cones,Pthere is U ⊆ {1, ..., m + 1} of size d + 1, and0
non-negative
β1 , ..., βm+1 such that w0 = Pm+1
t = 0 for all t 6∈ U , so thatt=1 βt yt xt and β
P
P
m+1
0
0
∗
w = t∈U βt yt xt . Unwrapping this, w = t=1 βt yt xt and m+1
t=1 βt yt = 0.
Now, consider the case, for some s 6∈ U , that (xs , ys ) is the test example. Using the βt ’s
for s 6= t, in part since βs = 0, w∗ and b∗ still satisfy the Karush-Kuhn-Tucker conditions
for a global optimum for the optimization problem obtained by excluding example number
s. Thus, the hyperplane parameterized by w∗ and b∗ is output when (xs , ys ) is the test
example, and xs was classified correctly by w∗ and b∗ . Since this holds for all s 6∈ U , thelinear SVM only makes mistakes on elements of U , and, since |U | ≤ d + 1, this completes
the proof.

Appendix B. Detailed definition of a learner
A learner can be built using any probability space (Ω, Σ, P ) as a source of randomness. It
is a function from Ω × (Rd × {−, +})∗ to Fd . Associated with each learner A is a predictor
φA that maps Ω × (Rd × {−, +})∗ × Rd to {+, −} defined by φA (ω, S, x) = (A(ω, S))(x).
For any finite number m of examples, the restriction of φA to the case of training sets ofsize m must be measurable with respect to the product distribution of (Ω, Σ, P ) and any
m + 1-fold product distribution used to generate the training examples and the test point;
the distributions used to generate examples use the Lebesgue σ-algebra.

References
András Antos and Gábor Lugosi. Strong minimax lower bounds for learning. Machine
Learning, 30(1):31–56, 1998.
Anselm Blumer and Nick Littlestone. Learning faster than promised by the vapnikchervonenkis dimension. Discrete Applied Mathematics, 24(1-3):47–53, 1989.
Bernhard E Boser, Isabelle M Guyon, and Vladimir N Vapnik. A training algorithm for
optimal margin classifiers. In Proceedings of the fifth annual workshop on Computational
learning theory, pages 144–152. ACM, 1992.
Nello Cristianini, John Shawe-Taylor, et al. An introduction to support vector machines andother kernel-based learning methods. Cambridge university press, 2000.
Luc Devroye and Gábor Lugosi. Lower bounds in pattern recognition and learning. Patternrecognition, 28(7):1011–1018, 1995.
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, and Leslie Valiant. A general lower
bound on the number of examples needed for learning. Information and Computation,
82(3):247–261, 1989.
David Haussler, Nicholas Littlestone, and Manfred K Warmuth. Predicting {0, 1}-functions
on randomly drawn points. Information and Computation, 115(2):248–292, 1994.
David P. Helmbold and Philip M. Long. New bounds for learning intervals with implications
for semi-supervised learning. In Proceedings of the 25th Annual Conference on Learning
Theory, volume 23 of Proceedings of Machine Learning Research, pages 30.1–30.15, 2012.
8

Complexity of Learning Linear Classifiers

Yi Li, Philip M Long, and Aravind Srinivasan. The one-inclusion graph algorithm is nearoptimal for the prediction model of learning. IEEE Transactions on Information Theory,
47(3):1257–1261, 2001.
Philip M Long. On the sample complexity of PAC learning half-spaces against the uniform
distribution. IEEE Transactions on Neural Networks, 6(6):1556–1559, 1995.
Manfred Opper and David Haussler. Calculation of the learning curve of bayes optimalclassification algorithm for learning a perceptron with noise. In Annual Workshop on
Computational Learning Theory: Proceedings of the fourth annual workshop on Computational learning theory, volume 5, pages 75–87, 1991.
Ohad Shamir. The sample complexity of learning linear predictors with the squared loss.
The Journal of Machine Learning Research, 16(1):3475–3486, 2015.
Maurice Sion and Philip Wolfe. On a game without a value. Contributions to the theory ofgames, 3:299–306, 1957.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast
rates. In Advances in neural information processing systems, pages 2199–2207, 2010.
J. von Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295–
320, 1928.

9