arXiv:1606.08920v2 [cs.LG] 31 Dec 2017

Exact Lower Bounds for the Agnostic
Probably-Approximately-Correct (PAC)
Machine Learning Model
Aryeh Kontorovich and Iosif Pinelis
Department of Computer Science
Ben-Gurion University
Beer Sheva, Israel 84105
e-mail: karyeh@cs.bgu.ac.il
Department of Mathematical Sciences
Michigan Technological University
Houghton, Michigan 49931-1295 U.S.A.
e-mail: ipinelis@mtu.edu
Abstract: We provide an exact non-asymptotic lower bound on the minimax expected excess risk (EER) in the agnostic probably-approximatelycorrect (PAC) machine learning classification model and identify minimax
learning algorithms as certain maximally symmetric and minimally randomized “voting” procedures. Based on this result, an exact asymptotic
lower bound on
√ the minimax EER is provided. This bound is of the simple form c∞ / ν as ν → ∞, where c∞ = 0.16997 . . . is a universal constant, ν = m/d, m is the size of the training sample, and d is the Vapnik–
Chervonenkis dimension of the hypothesis class. It is shown that the differences between these asymptotic and non-asymptotic bounds, as well as
the differences between these two bounds and the maximum EER of any
learning algorithms that minimize the empirical risk, are asymptotically
negligible, and all these differences are due to ties in the mentioned “voting” procedures. A few easy to compute non-asymptotic lower bounds on
the minimax EER are also obtained,
√ which are shown to be close to the
exact asymptotic lower bound c∞ / ν even for rather small values of the
ratio ν = m/d. As an application of these results, we substantially improve
existing lower bounds on the tail probability of the excess risk. Among the
tools used are Bayes estimation and apparently new identities and inequalities for binomial distributions.
AMS 2010 subject classifications: Primary 68T05, 62C20, 62C10,
62C12, 62G20, 62H30; secondary 62G10, 62C20, 91A35, 60C05.
Keywords and phrases: PAC learning theory, classification, generalization error, minimax decision rules, Bayes decision rules, empirical estimators, binomial distribution.

1. Introduction
The Probably Approximately Correct (PAC) model aims at providing a clean,
plausible and minimalistic abstraction of the supervised learning process [25, 24].
∗ January

3, 2018

1

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

2

In this paper we are concerned with the version of this model most commonly
appearing in modern literature, agnostic PAC [9, 12, 11].
Let X be an arbitrary nonempty set. The objective is to classify the elements
of the set X into two classes, by attaching a label 1 or −1 to each x ∈ X . Let
Y := {−1, 1}, the set of labels. Then a possible classification rule may be
identified with a map h : X → Y , called a hypothesis. Usually, hypotheses are
restricted to be elements of a specified subset H of the set Y X of all maps of
X to Y ; this subset H is called the hypothesis class.
It is assumed that there exists a true (but unknown to us) probability distribution, say D, on the set X × Y of all pairs (x, y) with x ∈ X and y ∈ Y .
To avoid tedious matters of measurability, let us just assume that the set X is
finite.
In the agnostic PAC model, considered in this paper, it is assumed that
the distribution D may be of completely arbitrary form, and the only information about it is provided to us by the “sample” values of a labeled sample
D
, YmD ) of m independent copies of a random pair
(X1D , Y1D ), . . . , (Xm
D
D
(X , Y ); here and in what follows, the superscript indicates the distribution
of the random pair.
The classification error probability for a hypothesis h ∈ H is
err(h, D) := P(h(X D ) 6= Y D ).

(1.1)

It should be clear that the least possible error probability
errmin (D) := errmin,H (D) := min err(h, D)
h∈H

(1.2)

will usually be strictly greater than 0, even when the true distribution D is
known.
In the agnostic PAC model, considered here, the only information about
the unknown distribution D is provided by the values of the sequence of m
independent random pairs

D
D
Zm
:= (X1D , Y1D ), . . . , (Xm
, YmD ) .
(1.3)
Therefore, the available “learning” strategies are the mappings
L : (X × Y )m → H ,
called learning algorithms.
Let hD denote any minimizer of err(h, D) over h ∈ H . Of course, hD is
unknown, since the distribution D is unknown. However, it may be reasonable
to use the plug-in estimator hD̂m of hD , obtained by substituting for D the
empirical distribution D̂m = D̂m (zm ) based on a “realization”

zm := (x1 , y1 ), . . . , (xm , ym ) ∈ (X × Y )m
(1.4)
of the “random sample” Zm from the distribution D. That is,

D
hD̂m = LERM Zm
,

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

3

where LERM is an empirical risk minimizer, that is, any learning algorithm such
that for each given sequence zm ∈ (X ×Y )m , the corresponding value LERM (zm )
of LERM is a minimizer in h ∈ H of the “empirical risk”
err(h, D̂m ) =

m
1 X
I{h(xi ) 6= yi }.
m i=1

Such a minimizer need not be unique, and so, the “empirical minimization”
learning algorithm LERM does not have to be unique.
A nontrivial question to ask here is how well the empirical risk minimizer
hD̂m performs compared to the best possible hypothesis, hD — that is, how
large the excess risk ∆(hD̂m , D) is, where
∆(h, D) := err(h, D) − errmin (D) = err(h, D) − err(hD , D).

(1.5)

This question has been to a large extent resolved. In particular, Theorem 4.9
from [1] (slightly restated here) provides the following upper bound on the tail
probabilities for the excess risk.
Theorem A. There is a universal real constant c > 0 such that for all finite
sets X , all distributions D on X × Y , all sample sizes m, and all hypothesis
classes H ⊆ Y X of VC dimension d, we have


D
P ∆ LERM (Zm
), D ≥ cu ≤ exp{−(mu2 − d)+ }
(1.6)
for all real u ≥ 0, where z+ := 0 ∨ z for real z.
See [1] for an account of the intermediate steps leading up to the highly nontrivial result presented in Theorem A; milestones here include the seminal paper
[25] by Vapnik and Chervonenkis, followed, notably, by work of Talagrand [22],
Haussler [10], and Long [15].
Recall that the VC dimension (that is, the Vapnik–Chervonenkis dimension)
of a set H ⊆ Y X is the largest nonnegative integer k such that there is a
subset of X of cardinality k that is shattered by H ; and a subset X0 of X is
said to be shattered by H if the set of the restrictions to X0 of all the functions
h ∈ H coincides with the entire set Y X0 of all functions from X0 to Y .
In what follows, d will always denote VC(H ), the VC dimension of H . The
case d = 0 may occur only if the cardinality of H is at most 1, so that there is at
most one hypothesis to choose. This trivial case will be excluded in the sequel;
that is, we shall assume that d = 1. Then, in particular, one can introduce the
fundamental ratio
ν := m/d
(1.7)
of the sample size m to the VC dimension d.
Lower bounds matching, up to constant factors, the upper bound given in
Theorem A are also known. The one with the apparently best currently known
numerical constants was given in [1, Theorem 5.2], which can be restated as
follows.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

4

Theorem B. If ν = m/d ≥ 642 /320 = 12.8, then for any finite set X , any
hypothesis class H ⊆ Y X of VC dimension d, and any learning algorithm
L : (X × Y )m → H , there is a distribution D on X × Y such that


1
1 
D
≥
.
P ∆ L(Zm
), D > √
64
320ν

(1.8)

This lower bound is also the culmination of a notable historical development
[25, 6, 20], detailed in [1].
Remark 1.1. In [19, Section 28.2.2] a much better constant factor, 1/8, was
claimed in place of 320 in (1.8). However, there is a mistake in the calculation;
the actual value of the constant furnished by the proof is 512.
Introduce the expected excess risk (EER)

D
R(L, D) := Rm (L, D) := E ∆ L(Zm
), D .
(1.9)
Let D := DX and L := LX ;m,H denote, respectively, the set of all distributions on X × Y and the set of all learning algorithms L : (X × Y )m → H ;
recall here that Y = {−1, 1}. Let then
p
sup Rm (L, D),
m/d sup sup
inf
cUB
m,d :=
X VC(H )=d L∈LX ;m,H D∈DX

cLB
m,d :=

p

m/d inf

inf

inf

(1.10)

sup Rm (L, D),

X VC(H )=d L∈LX ;m,H D∈DX

where supX and inf X are taken over all finite sets X , and supVC(H )=d and
inf VC(H )=d are taken over all hypothesis classes H of VC dimension d. The
quantity inf L∈L supD∈D Rm (L, D) may be referred to as the minimax EER.
Integrating both sides of inequality (1.6) in u ≥ 0, one sees that
p
cUB := sup cUB
m/d sup sup
sup Rm (LERM , D) < ∞, (1.11)
m,d ≤ sup
m,d

X VC(H )=d D∈DX

m,d

where supm,d is taken over all natural m and d; an exact calculation of cUB
seems to be beyond the reach of current methods.
It is also clear that inequality (1.8) implies
cLB
ν≥12.8 >

1
√
= 0.000873 . . . > 0,
64 320

(1.12)

LB
where cLB
ν≥ν∗ := inf{cm,d : m/d ≥ ν∗ }. for any real ν∗ > 0. A remarkable fact
that follows from (1.11) and (1.12) is that
UB
0 < lim inf cLB
m,d ≤ lim sup cm,d < ∞;
m/d→∞

m/d→∞

that is, the upper and lower bounds on the minimax EER are of the same order
of magnitude. Establishing an appropriate lower bound on the EER, R(L, D),
was the crucial part of the proof of Theorem B.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

symbol
B(m, d)

brief description
expression for inf

B0 (m, d)
B1 (ν)
B2 (ν)
B̃2 (ν), B̂2 (ν)
\ b)
bayes(k,

lower bound on B(m, d)
lower bound on B0 (m, d)
lower bound on B1 (ν)
lower bounds on B2 (ν)
Bayes risk for d = 1

(2.21)
(2.26)
(2.28)
(2.30), (2.32)
(2.14); (3.2)

bayes(κ, b)
b ∈ [−1, 1]
β(x)
LB
cUB
m,d [cm,d ]

convex minorant of bayes(k, b)
Y -bias for X = {1}
conditional Y -bias at x ∈ X
ν× (exact upper [lower] bound
on the minimax EER)
limit value of cLB
m,d
close lower bounds on cLB
m,d

Proposition 2.8
symbols sk (b), . . .
(2.3)

c∞ = 0.16997 . . .
cν , c̃ν
Ci
D, Dp,β
d := VC(H )
∆(h, D)
err(h, D)
errmin (h, D)
h: X → Y
H
I{·}
L
LERM , L∗ERM
L
Lrand
m
N
Nxp
ν := m/d
p
R(L, D), R(L; p, β)
sgn
sk (b)
Vkb , Yib
Vxp,β
(XiD , YiD ), (Xip , Yip,β )
X
Y = {−1, 1}
D
p,β
Zm
, Zm
z∗ = 0.75179 . . .

sup Rm (L, D)

L∈Lrand D

distribution on X × Y
VC dimension of H
excess risk
error probability
minimum error probability
hypothesis
hypothesis class
indicator function
learning algorithm (l.a.)
empirical risk minimizer
set of all non-randomized l.a.’s
set of all randomized l.a.’s
labeled sample size
binomial r.v. w/ parameters m, 1/d
cardinality of the set {i : Xi = x}
fundamental ratio
X -marginal of D
expected excess risk (EER)
modified sign function

“vote balance” at x ∈ X
labeled sample items
set of objects to classify
set of classification labels
labeled sample
√ 
maximizer of z2 1 − erf(z/ 2)

appears in/on
(2.13)

(1.10)
(2.1)
(2.29), (2.30)
(2.29), (A.12)
p. 2, p. 8
p. 3
(1.5)
(1.1)
(1.2)
p. 2
p. 2, p. 7
below (2.6)
p. 2
p. 3, (2.7), (2.11)
p. 4, p. 9
p. 9
p. 2
Theorem 2.5
Theorem 2.2; (3.5)
(1.7)
(2.3)
(1.9), (2.10)
below (2.6)
(2.15)
(2.16)
(2.20)
p. 2, p. 8
p. 2, p. 7
p. 2
(1.3), (2.4)
(2.27)

Table 1. Notations. The places where the symbols are first introduced are underlined.

5

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

6

A few words on the organization of the rest of this paper: The main results
are stated and discussed in Section 2. All necessary proofs are given in Section 3,
with more technical parts deferred further, to Appendices A–B.
An index of symbols used in this paper non-locally is given in Table 1, which
lists the places where the selected symbols are first introduced and, for a few
of the symbols, the places where those symbols are generalized, specialized, or
otherwise modified.
2. Results: statements and discussion
In this paper, we present optimal lower bounds on the minimax EER, which
cannot be further improved. Our main result is Theorem 2.2, which provides
an expression of the exact, non-asymptotic lower bound on the minimax EER.
This expression is in terms of a certain function bayes(k, b), which is the Bayes
risk for d = 1. We show (in Proposition 2.8) that bayes(k, b) has a certain convexity property with respect to k. Further important properties of the function
bayes, based on certain apparently novel identities and inequalities for binomial
distributions, are presented in Appendix A. Thus, the expression of the nonasymptotic lower bound on the minimax EER given in Theorem 2.2 becomes
amenable to high-precision analysis. Implicitly, the function bayes is present in
[3], butthere it was bounded via Pinsker’s inequality, which yields sub-optimal
results.
In particular, based on Theorem 2.2 and the mentioned analysis of the function bayes, we determine (in Theorem 2.4) the asymptotics of the just mentioned
exact lower bound:
√ 
z
(2.1)
cLB
m,d → c∞ := max 2 1 − erf(z/ 2) = 0.16997 . . .
z>0

whenever m and d vary in such a way that ν = m/d → ∞; here, as usual, erf
Ru
2
denotes the Gauss error function, given by the formula erf(u) := √2π 0 e−t dt
for real u ≥ 0.
It should be noted that in Theorem 2.2 randomization of learning algorithms
is allowed; however, it will also be shown (in Theorem 2.4) that the effect of this
randomization is asymptotically negligible and is entirely explained by ties in a
certain “voting” procedure.
Theorems 2.5, 2.9, 2.11, and Proposition 2.13 present, for finite m and d,
tractable lower bounds on cLB
m,d ; Theorem 2.16 then shows that all these lower
LB
bounds on cLB
,
as
well
as
c
m,d
m,d itself, converge to the limit constant c∞ in (2.1).
Moreover, it is shown (see Remarks 2.7 and 2.14, and Figure 2) that these lower
LB
bounds on cLB
m,d , as well as cm,d itself, are actually close to the limit value c∞
even for rather small values of ν = m/d.
The above discussion suggests a sense of completion in the area of lower
bounds for the PAC model. However, results and techniques presented here may
be used elsewhere. In fact, they already found an application in [14, Theorem
7.1], where existing lower bounds were not sufficiently delicate for the desired
parameter regime.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

7

In this paper, we apply our lower bounds on the EER to obtain substantial
improvements of the existing lower bounds on the tail probability of the excess
risk, as follows:
Theorem 2.1.
(i) Keeping the constants 12.8 and 320 in Theorem B in place, one can im1
prove the lower bound 64
≈ 0.0156 on the tail probability in (1.8) to 0.238.
1
(ii) Keeping the constants 12.8 and 64
in Theorem B in place, one can improve
the constant 320 in (1.8) to 41.3.
(iii) If the restriction ν ≥ 12.8 in Theorem B is relaxed to ν ≥ 3, then the
improved values 0.238 and 41.3 of the constants get only slightly worse:
0.227 and 49.6, respectively.
To state our results, let us introduce some additional notation and conventions to be used in the sequel.
Let 00 := 1.
For any α and ω in Z ∪ {∞}, let α, ω := {i ∈ Z : α ≤ i ≤ ω}. For any
m ∈ 0, ∞, let [m] := 1, m. In particular, [0] = ∅.
As usual, for any two sets S and T , let S T denote the set of all maps from T
to S.
For any set A and any k ∈ 0, ∞ we identify the k-tuples v = (v1 , . . . , vk ) ∈ Ak
with functions v : [k] → A, by the formula v(x) := vx for all x ∈ [k]; thus, we
identify the set Ak of k-tuples with the set A[k] of functions. So, we use notations
v(x) and vx interchangeably. We shall also identify a function with its graph.
As usual, the sum of the empty family of elements of a linear space is defined
as the zero element of that space.
The new results obtained in this paper all concern the lower bound cLB
m,d ,
p
defined in (1.10), on the minimax EER times the factor m/d, including the
limit behavior of cLB
m,d as m/d → ∞.
It is not hard to show (see Appendix B for details) that the defining expression
for cLB
m,d in (1.10) can be simplified as follows:
p
m/d inf sup Rm (L, D),
(2.2)
cLB
m,d =
L

D

where from now on it will be assumed (unless otherwise specified) that
X = [d],

H = Y X = {−1, 1} ,
[d]

inf :=
L

inf

L∈L[d];m,Y [d]

,

sup := sup ,
D

D∈D[d]

so that inf L is taken over all learning algorithms L : ([d] × Y )m → Y [d] and
supD is taken over all distributions D on [d] × Y . Accordingly, from now on we
[d]
shall use X and H interchangeably with [d] and Y X = {−1, 1} , respectively.
Note next that any distribution D on X × Y is completely characterized by
the two maps, say p = pD : X → [0, 1] and β = βD : X → [−1, 1], such that
 1 yβ(x) 
P(X D = x, Y D = y) = D({(x, y)}) = p(x)
+
(2.3)
2
2

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

8

for x ∈ X = [d] and y ∈ Y = {−1, 1}. Clearly then, one must have pD (x) =
P(X D = x) for all x ∈ X and βD (x) = 2 P(Y D = 1|X D = x) − 1 for all
x ∈ X with pD (x) 6= 0; if pD (x) = 0 for some x ∈ X , then the value of βD (x)
can be chosen arbitrarily in [−1, 1], So, the distribution of the random variable
(r.v.) X D is completely characterized by the map p = pD . Therefore, in what
follows let us write D = Dp,β if pD = p and βD = β, and, in the case when
D = Dp,β , let us simply write X p , Y p,β , Xip , Yip,β instead of X D , Y D , XiD , YiD
p
(respectively), assuming that the random pairs (X1p , Y1p,β ), . . . , (Xm
, Ymp,β ) are
p
p,β
D
D
independent copies of the random pair (X , Y ) = (X , Y ); let us then also
write

p,β
D
p
Zm
:= Zm
:= (X1p , Y1p,β ), . . . , (Xm
, Ymp,β )
(2.4)
(cf. (1.3)).
Take next any h ∈ H = {−1, 1}[d] . It is well known (see e.g. [5, page 10])
that the function hβ ∈ {−1, 1}[d] given by the formula
hβ (x) := sgn βx

(2.5)

for x ∈ [d] is a minimizer of err(h, Dp,β ) over all h ∈ {−1, 1}[d] , and the excess
risk (relative to Dp,β ) of h over hβ is
∆(h, Dp,β ) = err(h, Dp,β ) − err(hβ , Dp,β ) =

d
X

px |βx | I{h(x) 6= hβ (x)}, (2.6)

x=1

where
sgn u := 2 I{u ≥ 0} − 1
for real u and I{·} is the indicator function.
Replacing now the unknown true distribution D = Dp,β by the empirical


distribution D̂m = D̂m (x1 , y1 ), . . . , (xm , ym ) for (x1 , y1 ), . . . , (xm , ym ) =:
z ∈ (X × Y )m , one sees that a function h ∈ {−1, 1}[d] is a minimizer of
c for all x ∈ X
err(h, D̂m ) for the given “sample” z if and only if h(x) = sgn pβ
x
P
m
1
c = 0 for some
c 6= 0, where pβ
c :=
yi I{xi = x}; if pβ
such that pβ
x

x

m

i=1

x

x ∈ X , then the value h(x) of a minimizer h (of err(h, D̂m )) at this point x can
be chosen arbitrarily in the set {−1, 1}. Thus, all the learning algorithms LERM
that are minimizers of the empirical risk are given by the formula
(
:= sgn vx if vx 6= 0,
LERM (zm )(x) := Lm,d; ERM (zm )(x)
(2.7)
∈ {−1, 1} if vx = 0
for all zm ∈ (X × Y )m and x ∈ X = [d], where
vx := vx (zm ) :=

m
X

c .
yi I{xi = x} = m pβ
x

(2.8)

i=1

Formula (2.7) states that the empirical risk is minimized when the value y ∈
{−1, 1} assigned by the learning algorithm at point x based on the “sample” zm

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

9

is decided by the majority vote vx = vx (zm ) “at x”, with the “voting” restricted
to the pairs (xi , yi ) with xi = x; if there is a tie (no majority) at x, then a value
y ∈ {−1, 1} at x is chosen arbitrarily.
To decrease the risk and also be able to fully use the power of decision
theory, one may randomize learning algorithms. A convenient way to define
such an algorithm L is to allow its value (which is a function in H ) to depend, not only on the nonrandom “sample” zm = (x1 , y1 ), . . . , (xm , ym ) ∈
(X × Y )m as in (1.4), but also on the value u of another r.v., say U , which is
(say) uniformly distributed on the interval [−1,1] and independent of the ranD
D
dom “sample” Zm
= (X1D , Y1D ), . . . , (Xm
, YmD ) as in (1.3). Thus, a randomized
learning algorithm L will be understood as a map from (X × Y )m × [−1, 1] to
H.
Let Lrand = Lrand,d and L = Ld denote, respectively, the set of all randomized learning algorithms and the set of all non-randomized ones. The definition
(1.9) of the EER (for L ∈ L ) is naturally extended as follows:

D
R(L, D) := Rm (L, D) := E ∆ L(Zm
, U ), D
(2.9)
for L ∈ Lrand ; it then follows by (2.6) that
Rm (L; p, β) := Rm (L, Dp,β ) =

d
X


p,β
px |βx | P L(Zm
, U )(x) 6= hβ (x) .

(2.10)

x=1

Of particular importance will be the following “maximally symmetric” and
“minimally randomized” version of the learning algorithms LERM that are minimizers of the empirical risk (cf. (2.7)):


 sgn vx if vx 6= 0,
∗
∗
if vx = 0 but nx 6= 0,
LERM (zm , u)(x) := Ld,ERM (zm , u)(x) := yix


sgn u if nx = 0
(2.11)
for (zm , u) ∈ (X × Y )m × [−1, 1] = ([d] × {−1, 1})m × [−1, 1], where
nx := nx (zm ) :=

m
X

I{xi = x}

and ix := ix (zm ) := min{i ∈ [m] : xi = x}.

i=1

(2.12)
That is, the choice of the value of L∗ERM (zm , u)(x) in Y = {−1, 1} is decided
by the majority vote “at x” if there is a majority there; otherwise, the value
L∗ERM (zm , u)(x) is the same as that of the first voter that appeared “at x” if
any one did; finally, if no one arrived to vote “at x”, then the value is decided
by a flip of a fair coin, the flip being independent of any voters. Thus, randomization according to the learning algorithm L∗ERM occurs only if no one shows
up for voting at some location x ∈ X . Yet, this minimal (and, one may argue,
quite natural) randomization is enough to make L∗ERM a winner (that is, a minimax learning algorithm) against all randomized (and non-randomized) learning
algorithms. A precise formulation of this thesis is contained in

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

10

Theorem 2.2. Take any m ∈ 0, ∞. Then
inf

sup Rm (L, D) = sup Rm (L∗ERM , D)

L∈Lrand D

D

= B(m, d) := sup

d
X

p,β x=1

px |βx | E bayes(Nxp , |βx |), (2.13)

Pd
where supp,β is taken over all pairs of functions p ∈ [0, 1][d] such that x=1 px =
1 and β ∈ [−1, 1][d] , Nxp is a r.v. with the binomial distribution with parameters
m and px ,

(2.14)
bayes(k, b) := 12 1 − sk (b) ,
sk (b) := | P(Vkb > 0) − P(Vk−b > 0)|,
Vkb

:= Y1b
P(Yib

+ ···

+ Ykb ,
= 1+b
2

(2.15)
(2.16)

and
= −1) = 1−b
and the
are iid r.v.’s with
= 1)
2 [=
1−P(Yib = 1)], for k ∈ 0, ∞ and b ∈ [−1, 1]. Moreover, for each pair of functions
p and β as described above,
Yib ’s

Rm (L∗ERM ; p, β) = Rm (L∗ERM , Dp,β ) =

d
X

P(Yib

px |βx | E bayes(Nxp , |βx |),

(2.17)

x=1

which does not depend on sgn β := (sgn β1 , . . . , sgn βd ).
The use of the symbol bayes in (2.13) is a reflection of the fact that the
minimax learning algorithm L∗ERM is a Bayes one with respect to a certain prior
distribution on the set of all distributions D on X × Y ; see the beginning of
the proof of Theorem 2.2 in Section 3 for details on this. Formula (2.17) means
that the learning algorithm L∗ERM has an important risk-equalizing property —
which actually makes the Bayes decision rule L∗ERM minimax; cf. e.g. Theorem 3
and Lemma 1 in [7, §2.11].
Remark 2.3. It is clear from (2.14)–(2.15) that bayes ≤ 12 . Hence, by (2.13),
inf L∈Lrand supD Rm (L, D) ≤ 21 .
It turns out, as may be expected, that the effect of the randomization of learning algorithms is asymptotically negligible whenever ν = m/d → ∞; that is, the
difference inf L∈L supD − inf L∈Lrand supD is asymptotically negligible compared
with the “non-randomized” minimax EER inf L∈L supD . Moreover, all the learning algorithms of the form LERM as in (2.7) that are minimizers of the empirical
risk are asymptotically minimax. These facts — along with the asymptotics of
the minimax risk — are presented in
Theorem 2.4. For each pair (m, d) of natural numbers, choose any learning
algorithm of the form Lm,d;ERM , as in (2.7). Then
c
p ∞ ∼ inf sup Rm (L, D) ≤ inf sup Rm (L, D)
L∈L D
m/d L∈Lrand D
c∞
≤ sup Rm (Lm,d;ERM , D) ∼ p
m/d
D

(2.18)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

11

whenever m/d → ∞, where c∞ = 0.16997 . . . as in (2.1). Moreover,
0 ≤ sup Rm (Lm,d;ERM , D) −
D

≤

inf

sup Rm (L, D)

L∈Lrand D

d
 1 
 1 
X

1
=o p
, (2.19)
sup
px |βx | P Vxp,β = 0 = O
2 p,β x=1
m/d
m/d

again whenever m/d → ∞, where
Vxp,β :=

m
X

Yip,β I{Xip = x},

(2.20)

i=1
p,β
the vote “balance” at x based on the random “sample” Zm
as in (2.4).

Here, as usual, the asymptotic equivalence A ∼ B means A/B → 1.
Display (2.19) shows that the (asymptotically negligible) pairwise differences
between (i) the minimax EER inf L∈L supD Rm (L, D), (ii) its “randomized” version inf L∈Lrand supD Rm (L, D), and (iii) the maximum risk supD Rm (Lm,d;ERM , D)
of any empirical-risk-minimizing learning algorithms of the form LERM are entirely explained by ties in the mentioned “voting”, when the “no-majority” event
Vxp,β = 0 occurs for at least one x ∈ X = [d].
It is obvious from (2.13) that
B(m, d) ≥

d
X
1
b E bayes(Nx , b) = b E bayes(N1 , b)
d
x=1

for any b ∈ [0, 1], where Nx stands for Nxp with px =
view of (2.18), one immediately obtains

1
d

for all x ∈ [d]. Thus, in

Theorem 2.5.
inf sup Rm (L, D) ≥

L∈L

D

inf

sup Rm (L, D) ≥ B0 (m, d) := sup b E bayes(N, b),

L∈Lrand D

b∈[0,1]

(2.21)
where N is a binomial r.v. with parameters m and 1/d.
Recall (2.4) and let
Dβ := Dp,β

β
p,β
and Zm
:= Zm

when px =

1
d

for all x ∈ X = [d].

Theorem 2.6. For any b ∈ [0, 1],
X
1
inf
R(L, Dβ ) = b E bayes(N, b).
d
L∈Lrand 2
[d]

(2.22)

(2.23)

β∈{−b,b}

As we shall see, Theorem 2.6 follows immediately from the proof of Theorem 2.2. On the other hand, Theorem
2.6 could be viewed as a refinement of
P
Theorem 2.5, because clearly 21d β∈{−b,b}[d] R(L, Dβ ) ≤ supD R(L, D) for any
L. Even though the refinement is slight, Theorem 2.6 will be useful, in particular,
in the proof of Theorem 2.1.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

12

Remark 2.7. Note that, by (2.14)–(2.15), bayes(k, b) is a polynomial in b of
degree ≤ k. Hence, b E bayes(N, b) is a polynomial in b of degree ≤ m + 1, and
so, the lower bound B0 (m, d) in (2.21) is an algebraic number, which is not
phard
to compute unless m is too large. For instance, for c0 (m, d) := B0 (m, d) m/d
we find
c0 (5, 2) = 0.16757 . . . ,

c0 (50, 20) = 0.17467 . . . ,

and c0 (50, 2) = 0.16968 . . .
(2.24)
(with the execution times in Mathematica about 0.02 sec, 1.4 sec, and 1 sec,
respectively). One may note that, even for such a rather small value 5/2 =
50/20 = 2.5 of ν = m/d, the values of c0 (m, d) are close to the limit value
c∞ = 0.16997 . . . — cf. (2.1) and (2.18). However, more work needs to be done
to more fully understand the manner in which the lower bound B0 (m, d) depends
on m and d.
The important first step toward this goal is establishing the following convexity property of the function k 7→ bayes(k, b).
\
\
Proposition
2.8. Take any
b ∈ [0, 1]. Then the largest convex function [0, ∞) 3
κ 7→ bayes(κ, b) such that bayes(k, b) ≤ bayes(k, b) for all k ∈ {0, 1, . . . } is given
by the formula
\
bayes(κ, b)
(
(1 − κ) bayes(0, b) + κ bayes(1, b) = 12 (1 − κb)
if 0 ≤ κ ≤ 1,
:= 2i+3−κ
κ−2i−1
bayes(2i + 1, b) +
bayes(2i + 3, b) if 2i + 1 ≤ κ ≤ 2i + 3
2
2
(2.25)
for any i ∈ 0, ∞.

\

That is, the largest convex minorant bayes(·, b) on [0, ∞) of the function
bayes(·, b) on {0, 1, . . . } is just the linear interpolation of bayes(·, b) at the points
0, 1, 3, 5, . . . . This is illustrated in Figure 1.
Recall the definition (1.7) of ν. Using (2.21), Proposition 2.8, Jensen’s inequality, and the equality E N = ν, one immediately obtains
Theorem 2.9.

\

inf sup R(L, D) ≥ B0 (m, d) ≥ B1 (ν) := sup b bayes(ν, b).
L

D

(2.26)

b∈(0,1)

Here and in the rest of this section, inf L can be replaced by either inf L∈L or
inf L∈Lrand .
Remark 2.10. An advantage of the lower bound B1 (ν) in (2.26) over the bound
B0 (m, d) in (2.21) is that it depends only on ν = m/d; also, B1 (ν) is not hard
to compute unless ν is too large. Yet, the nature of the dependence of B1 (ν)
on ν may still seem rather obscure. Therefore, we are going to present a lower
bound on B1 (ν) that is much easier to grasp and yet is (i) asymptotic to the
original lower bound B0 (m, d) for ν = m/d → ∞ and (ii) close to B0 (m, d) even
for moderate values of ν = m/d.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

13

0.5
0.4
0.3
0.2
0.1

1

2

3

4

5

6

k, κ

7

\1. Graphs of the maps {0, 1, . . . , 7} 3 k 7→ bayes(k, b) (black dots) and [0, 7] 3 κ 7→
Fig
bayes(κ, b) (gray broken line) for b = 0.6.

In Appendix A, we shall obtain explicit and rather tight lower bounds on the
function bayes. In view of Theorem 2.9 and Proposition 2.8, this will result in
explicit lower bounds on the minimax excess risk inf L supD R(L, D), as follows.
Let
z∗ = 0.75179 . . .
(2.27)
√

be the unique maximizer of z2 1 − erf(z/ 2) in real z > 0, with the maximum
value c∞ = 0.16997 . . . , as in (2.1).
Theorem 2.11. Assume that ν ≥ 1. Let iν := b ν−1
2 c. Then
cν
inf sup R(L, D) ≥ B1 (ν) ≥ B2 (ν) := √ ,
L D
ν

(2.28)

where
√
z∗ 
erf(z∗ / 2) 
cν :=
1 − C iν
< c∞
2
exp{−z∗2 /(6ν)}

p

 
2i
and Ci =
i
(2.29)
for i = 0, 1, . . . . Moreover, for ν ≥ 3, B2 (ν) admits a simple lower bound on it:
√
 

z∗
iν + 1 1/8 erf(z∗ / 2)
c̃ν
1−
≤ cν .
B2 (ν) ≥ B̃2 (ν) := √ , where c̃ν :=
2
iν
exp{−z∗2 /(6ν)}
ν
(2.30)

Remark 2.12. To obtain the second inequality in (2.28) B1 (ν) ≥ B2 (ν) , in
the proof of Theorem 2.11 we are going to use, in particular, two facts: (i)
p that
Ci decreases in i (as stated in Lemma A.2) and (ii)
the
concavity
of
erf(b
k/2)
p
in k. If one also uses the obvious fact that erf(b k/2) increases in k, then, by
π(i + 1/2)
22i

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

14

Chebyshev’s integral inequality,
q
q


2i+3
(1 − wi )Ci erf b 2i+1
+
w
C
erf
b
i
i+1
2
2
q
q




2i+3
≤ (1 − wi )Ci + wi Ci+1 (1 − wi ) erf b 2i+1
+
w
erf
b
i
2
2


√
≤ (1 − wi )Ci + wi Ci+1 erf(b ν),
where i := iν and wi := ν−2i−1
∈ [0, 1). Thus, one can replace Ciν = Ciν ∨Ciν +1
2
in (2.29) by the smaller (and hence better) value (1−wi )Ci +wi Ci+1 , with i = iν .
1/8
= C̃iν ∨ C̃iν +1 in (2.30) by the
Quite similarly, one can replace C̃iν := iνi+1
ν
smaller (and hence better) value (1 − wi )C̃i + wi C̃i+1 , with i = iν . However,
these improvements are comparatively small, especially for larger values of ν,
and the resulting expressions will be less easy to perceive.
It is clear that
cν → c∞ and c̃ν → c∞
(2.31)
as ν → ∞. In fact, cν and even c̃ν are rather close to c∞ already for rather small
values of ν. E.g., one has c5 = 0.15536 . . . , c̃5 = 0.15514 . . . , c50 = 0.16852 . . . ,
and c̃50 = 0.16852 . . . , and indeed all these four values are rather close to c∞ =
0.16997 . . . . We also see that the values of c̃ν are not only simpler to compute
than, but also very close to, the corresponding values of cν .
Inequality (2.28) in Theorem 2.11 does not cover the case 0 < ν < 1, and
inequality (2.30) does not cover the case 0 < ν < 3. These two apparently less
important cases are covered, complementarily, by
Proposition 2.13.
inf sup R(L, D) ≥ B̂2 (ν) :=
L D

B1 (ν) = 12 (1 − ν)
if 0 < ν ≤ 12 ,




1
B1 (ν) = 8ν
if 12 ≤ ν ≤ 1,


2
3
4


 (17 − 2ν) 57187 − 3253ν − 138ν + 212ν − 8ν
if 1 ≤ ν ≤ 3.
6480000

(2.32)

Remark 2.14. In particular, B̂2 (1) = B1 (1) = 0.125, B̂2 (3) = 0.087018 . . . =
0.15072...
√
√
, and B1 (3) = 0.087019 . . . = 0.15072...
(cf. (2.28)). More generally, the
3
3
1
1
choices b = 1 for ν ∈ (0, 2 ] and b = 2ν for ν ∈ [ 12 , 1] in the proof of Proposition 2.13 are optimal, in the sense that B̂2 (ν) = B1 (ν) for ν ∈ (0, 1], as indicated
1
in (2.32). The choice b = 30
(17 − 2ν) for ν ∈ [1, 3] in the just mentioned proof
is nearly optimal; namely, then B̂2 (ν) > B1 (ν) − 2 × 10−6 , for all ν ∈ [1, 3]; see
details on this remark in Section 3, right after the proof of Proposition 2.13. Of
course, one can also rather easily give an exact algebraic expression for B1 (ν)
with ν ∈ [1, 3]; however, that expression (in terms of certain roots of certain
polynomials in one variable whose coefficients are polynomials in ν) is complicated and therefore omitted here.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

15

Theorem 2.11, Remark 2.12, relations (2.31), Proposition 2.13, and Remark 2.14 are illustrated in Fig. 2.
c ∞ , c ν , c ν

c ∞ , c ν , c ν , c ν,Cheb , c ν,Cheb
0.170

0.16

0.165
0.14

0.160
0.155

0.12

0.150
0.10
1.5

2.0

2.5

3.0

ν

5

10

15

20

ν

√
Fig 2. Left panel: graphs of cν (red) and ĉν := ν B̂2 (ν) (black) for ν ∈ [1, 3]. Right panel:
graphs of cν (red), c̃ν (green), cν,Cheb (blue), and c̃ν,Cheb (magenta) for ν ∈ [3, 20], where
cν,Cheb and c̃ν,Cheb are obtained from the expressions for cν and c̃ν in (2.29) and (2.30) by
1/8
replacing there Ciν and C̃iν = iνi+1
by the “Chebyshev” expressions (1−wi )Ci +wi Ci+1
ν

and (1 − wi )C̃i + wi C̃i+1 , with i = iν and wi := ν−2i−1
, as discussed in Remark 2.12. The
2
dotted horizontal line in both panels is at the level of c∞ = 0.16997 . . . .

Let us also present the following very simple, but suboptimal, lower bound
— cf. e.g. (2.18).
Proposition 2.15. If ν ≥

3
41 ,

then

0.125
inf sup R(L, D) ≥ B0 (m, d) ≥ √ .
L D
ν

(2.33)

3
Note that the restriction ν ≥ 41
in Proposition 2.15 cannot be dropped, and
it is in fact rather close to necessity. Indeed, in view of Remark 2.3, the lower
1
3
√
√
bound 0.125
in (2.33) cannot hold for ν < 16
= 48
. The lower bound 0.125
in
ν
ν
(2.33) was obtained by different methods in [2] (under the condition ν ≥ 14 ,
which was omitted from the paper but stated in a corrigendum).
In conclusion of this section, we summarize the asymptotic behavior of the
lower bounds B0 (m, d), B1 (ν), B2 (ν), B̃2 (ν) on the minimax EER, as well as the
asymptotic behavior of the minimax EER itself.

Theorem 2.16.
c
c
√∞ ∼ inf sup R(L, D) ≥ B0 (m, d) ≥ B1 (ν) ≥ B2 (ν) ≥ B̃2 (ν) ∼ √∞
L D
ν
ν

(2.34)

as m and d vary in any way such that ν = m/d → ∞.
Thus, in view of (2.2), the limit relation in (2.1) holds and, moreover, all the
lower bounds B0 (m, d), B1 (ν), B2 (ν), B̃2 (ν) on the minimax EER are asymptotically equivalent to the minimax EER itself whenever ν = m/d → ∞. Clearly,
Theorem 2.16 complements Theorem 2.4.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

16

3. Proofs
In this section, we shall prove (or provide details for) Theorems 2.2 and 2.6,
Proposition 2.8, Theorem 2.11, Proposition 2.13, Remark 2.14, Proposition 2.15,
Theorems 2.4 and 2.16 (together), and finally Theorem 2.1, in this order.
Proof of Theorem 2.2. The first equality in (2.13) can be obtained using the
von Neumann minimax duality theorem for bilinear functions on the product
of simplexes [23] (plus a certain symmetrization argument); more general minimax duality theorems, for convex-concave-like functions, were given in [21], and
in [17] a necessary and sufficient condition for the minimax duality for such
functions was given.
However, here we are going to offer a more direct and explicit argument, using
the explicit form of the to-be-proved-minimax decision rule L∗ERM , as defined in
(2.11).
To gain some insight, let us begin with the simple case d = 1. In that case,
X = [d] = [1] = {1}, p = (1) (that is, p1 = 1) and β = (b) with b := β1 ∈ [−1, 1];
also, in the just mentioned definition
(2.11) of L∗ERM , the terms x, vx , ix , and
Pm
nx simplify, respectively, to 1, v1 = i=1 yi , 1, and n1 = m, in accordance with
the definitions of vx , ix , and nx in (2.8) and (2.12). Here we also have Xi = 1
p,β
for all i and hence, in view of (2.4) and (2.3), Zm
equals

b
Zm
:= (1, Y1b ), . . . , (1, Ymb )
(3.1)
in distribution, where the Yib ’s are as in the statement of Theorem 2.2.
A standard argument (see e.g. [7, §1.8]) shows that L∗1,ERM is an optimal
Bayesian decision rule, in the sense of being a minimizer of the average

P
|b|y
1
P L(Zm , U )(1) 6= y of the types I and II error probabilities over all
2
y∈Y

L ∈ Lrand,1 , that is, over all randomized learning algorithms L for d = 1. By
symmetry, without loss of generality b ≥ 0, and so,

Pb ∈ [0,∗1]. Thenbyfor the corresponding Bayes risk, given by the expression 12
P L1,ERM (Zm , U )(1) 6= y ,
y∈Y

for m ≥ 1 one has

P
|b|y
2 · 12
P L(Zm
, U )(1) 6= y
y∈Y

≥2·

1
2

P

by
P L∗1,ERM (Zm
, U )(1) 6= y



y∈Y

= P(Vmb < 0) + P(Vmb = 0, Y1b < 0) + P(Vm−b > 0) + P(Vm−b = 0, Y1−b > 0)
= P(Vmb < 0) + P(Vmb = 0) + P(Vm−b > 0) = P(Vmb ≤ 0) + P(Vm−b > 0)

=1 − P(Vmb > 0) − P(Vm−b > 0) = 2 bayes(m, b),
(3.2)
in accordance with (2.16)  implying, in particular, that (Y1−b , Vm−b ) equals
(−Y1b , −Vmb ) in distribution , (2.14), (2.15), and the assumption b ∈ [0, 1] which

implies P(Vmb > 0) ≥ P(Vm−b > 0), since Yib is stochastically increasing in b .

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

Thus, the Bayes risk

1
2

P

17


by
P L∗1,ERM (Zm
, U )(1) 6= y equals bayes(m, b) for

y∈Y

b ∈ [0, 1] and m ≥ 1. This conclusion also trivially holds for m = 0 (in which
case bayes(m, b) = 12 ).
Moreover, for each m ∈ 0, ∞, the Bayes rule L∗1,ERM is a risk equalizer, in the
sense that

by
for b ∈ [0, 1] and y ∈ {−1, 1}, P L∗1,ERM (Zm
, U )(1) 6= y = bayes(m, b), (3.3)
which does not depend
follows because (i)
 on the choiceb of y; this conclusion
b −
b −
(L∗1,ERM (Zm
) , −U = −L∗1,ERM (Zm
, U ), where (Zm
) := (1, −Y1b ), . . . ,

(1, −Ymb ) , and (ii) the distribution of (Y1−b , . . . , Yk−b , −U ) is the same as that
of −(Y1b , . . . , Ykb , U ).
Let us now proceed to the general case of any natural d, which in a sense reduces to the case d = 1. Take any m ∈ 0, ∞, any randomized
Pd learning algorithm
L : (X × Y )m × [−1, 1] → H , any p ∈ [0, 1][d] such that x=1 px = 1, and any
β ∈ [−1, 1][d] . For each x ∈ [d], introduce the random set
Jxp := {i ∈ [m] : Xip = x}

(3.4)

Nxp := card Jxp .

(3.5)

and its cardinality
Then, by (2.10),
Rm (L; p, β) =

d
X
x=1

px |βx |

m
X



p,β
P L Zm
, U (x) 6= hβ (x), Nxp = k .

(3.6)

k=0

Next, take any x ∈ [d] and any k = 0, . . . , m. Then


p,β
P L Zm
, U (x) 6= hβ (x), Nxp = k
X


p,β
=
P L Zm
, U (x) 6= hβ (x), Jxp = J , (3.7)
J∈([m]
k )

where [m]
:= {J ⊆ [m] : card J = k}.
k

Further, take any set J ∈ [m]
k . Writing J as {i1 , . . . , ik } with i1 < · · · < ik ,
c
let XJp := (Xip1 , . . . , Xipk ), and similarly define XJpc , YJp,β , and YJp,β
:=
c , where J
p,β
p
p,β
J
[m] \ J. Let also ZJ c := (XJ c , YJ c ). For any x ∈ X , let x := (x, . . . , x) ∈ X k
and Zx := (X \ {x}) × Y . Then, in view of (2.5),


p,β
P L Zm
, U (x) 6= hβ (x), Jxp = J
X



p,β
=
P L Zm
, U (x) 6= sgn βx |XJp = xJ , ZJp,β
= z P XJp = xJ , ZJp,β
=z .
c
c
z∈Zxm−k

(3.8)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

18

Here and in what follows, to simplify the writing, we neglect the possibility
that P(XJp = xJ , ZJp,β
= z) may equal 0. Of course, in such cases we may let the
c
corresponding conditional probabilities in (3.8) take whatever values deemed
most suitable for us at any given point.
By (3.6), (3.7), and (3.8),
Rm (L; p, β) =

X



p,β
px |βx | P L Zm
, U (x) 6= sgn βx |XJp = xJ , ZJp,β
=z
c

x,k,J,z


× P XJp = xJ , ZJp,β
= z , (3.9)
c
P

where

:=

d
m
P
P

P

P

, and, moreover, the sum

x=1 k=0 J∈([m]) z∈Zxm−k
k

x,k,J,z

X


P XJp = xJ , ZJp,β
= z = P(Nxp = k)
c

(3.10)

J,z

where

P
J,z

P

:=

P



does not depend on β. To quickly see why identity

z∈Zxm−k
J∈([m]
k )


p,β
(3.10) holds, look back at (3.7) and (3.8), with the event {L Zm
, U (x) 6=
hβ (x)} replaced there by an event of probability 1.
p
, Ymp,β ), U are independent, for any L ∈ Lrand , x ∈
Since (X1p , Y1p,β ), . . . , (Xm

Pd
[m]
[d], k ∈ 0, m, J ∈ k , z ∈ Zxm−k , and p ∈ [0, 1][d] such that
x=1 px =


p
J
p,β
= z
1, the conditional probability P L Zm , U (x) 6= sgn βx |XJ = x , ZJp,β
c
in (3.8) depends on β only through βx , whereas the unconditional probability

P XJp = xJ , ZJp,β
= z in (3.8) depends on β only through β\x := β X \{x} — the
c
restriction of the function β to the subset X \ {x} of the set X . So, introducing
the averaging operators
X
X
X
1
1
1
ave := d
,
, ave := d−1
, ave :=
σ
σ\x
σx
2
2
2
[d]
X \{x}
σx ∈{−1,1}

σ\x ∈{−1,1}

σ∈{−1,1}

in view of (3.9) one has
ave Rm (L; p, |β|σ)
σ
X


p,|β|σ
p,|β|σ
=
px |βx | ave P L Zm
, U (x) 6= σx |XJp = xJ , ZJ c
=z
x,k,J,z

σx

p,|β|σ

× ave P XJp = xJ , ZJ c
σ\x


= z . (3.11)

p
Recall that the random pairs (X1p , Y1p,β ), . . . , (Xm
, Ymp,β ) are independent
p
p,β
D
D
copies of the random pair (X , Y ) = (X , Y ) satisfying condition (2.3),
and the r.v. U is independent of these pairs. So, for any x ∈ [d], k ∈ 0, m,

Pd
m−k
J ∈ [m]
, and p ∈ [0, 1][d] such that
x=1 px = 1, the conk , z ∈ Zx
p,β
p
J
ditional distribution of (YJ , U ) given XJ = x and ZJp,β
= z is the same
c

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

19

as the distribution of (Y1βx , . . . , Ykβx , U ), where the Yib ’s are again as in the
statement of Theorem 2.2. Therefore,
in view of (3.2), for each x ∈ [d], each

z = (xk+1 , yk+1 ), . . . , (xm , ym ) ∈ Zxm−k , and J = [k],
p,|β|σ

ave P L Zk
σx



p,|β|σ
, U (x) 6= σx |XJp = xJ , ZJ c
=z


|β |σ
= ave P Lx Zk x x , U (1) 6= σx ≥ bayes(k, |βx |), (3.12)
σx

where Zkb is as in (3.1) and Lx : ([1]×Y )k ×[−1, 1] → {−1, 1}[1] is the randomized
learning algorithm (for the case d = 1) defined by the formula
Lx ((1, y1 ), . . . , (1, yk )), u := h|{x} , the restriction of the function h to the sin
gleton set {x}, where h := hw;u := L w, u ∈ {−1, 1}[d] , w := (x, y1 ), . . . , (x, yk ),
(xk+1 , yk+1 ), . . . , (xm , ym ) , and u ∈ [−1, 1]. Clearly then, (3.12) holds for any

J ∈ [m]
k .
Similarly, but now using (3.3) instead of (3.2), we have


p,|β|σ
p,|β|σ
P L∗m,ERM Zm
, U (x) 6= σx |XJp = xJ , ZJ c
= z = bayes(k, |βx |) (3.13)
for each x ∈ [d] and each σx ∈ {−1, 1}, and hence the average of the left-hand
side (l.h.s.) of (3.13) over σx ∈ {−1, 1} equals bayes(k, |βx |) as well. Note also

p,|β|σ
that P XJp = xJ , ZJ c
= z does not depend on L. So, collecting identity
(3.11), its counterpart with L∗m,ERM in place of L, (3.12), and identity (3.13)
with its l.h.s. replaced by the average of that l.h.s. over σx ∈ {−1, 1}, we see
that
ave Rm (L; p, |β|σ) ≥ ave Rm (L∗m,ERM ; p, |β|σ).
(3.14)
σ

σ

Moreover, by (3.9) with
Rm (L∗m,ERM ; p, β) =

L∗m,ERM
X

in place of L, (3.13) with σ = sgn β, and (3.10),

px |βx | bayes(k, |βx |) P XJp = xJ , ZJp,β
=z
c



x,k,J,z

=

=

d
X

m
X

x=1

k=0

d
X

m
X

x=1

=

px |βx |

d
X

px |βx |

bayes(k, |βx |)

X

P XJp = xJ , ZJp,β
=z
c



J,z

bayes(k, |βx |) P(Nxp = k)

k=0

px |βx | E bayes(Nxp , |βx |),

x=1

(3.15)
which proves (2.17) and the second equality in (2.13) (here one may recall the
definition of Rm (L; p, β) in (2.10)). We also see that Rm (L∗m,ERM ; p, β) depends

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

20

on β only through |β|. This and (3.14) yield
max

σ∈{−1,1}d

=

d
X

Rm (L∗m,ERM ; p, |β|σ) = ave Rm (L∗m,ERM ; p, |β|σ)
σ

px |βx | E bayes(Nxp , |βx |) ≤ ave Rm (L; p, |β|σ) ≤
σ

x=1

max

σ∈{−1,1}d

Rm (L; p, |β|σ).

Taking now supp,β , we see that supD Rm (L∗m,ERM , D) ≤ supD Rm (L, D) for
all L, which proves the first equality in (2.13). This completes the proof of
Theorem 2.2.
Proof of Theorem 2.6. This theorem follows immediately from (3.14) and (3.15)
by taking there px = d1 for all x ∈ [d] and any β ∈ {−b, b}[d] .
Proof of Proposition 2.8. By (2.14)–(2.15), bayes(k, b) = 1/2 for all k = 0, 1, . . .
if b = 0. Suppose now that b ∈ (0, 1]. Letting k → ∞ and using the law of large
numbers, in view of (2.16) we have k1 Vkb → E Y1b = b > 0 in probability. So,
P(Vkb > 0) → 1; similarly, P(Vk−b > 0) → 0. Recalling (2.14)–(2.15) again, we
see that bayes(k, b) → 0. So, by Lemma A.1 in Appendix A, bayes(k, b) is convex
and nonincreasing in k ∈ {0, 1, 3, 5, . . . }, for each b ∈ [0, 1]. It remains to use
relations (A.9) and (A.7) in Appendix A and, again, (2.14).
Proof of Theorem 2.11. The first inequality in (2.28) comes from (2.26). The
second inequality
in (2.28) follows immediately from Lemma A.3 with κ = ν
√
and b = z∗ / ν. The inequality in (2.29) holds because, by Lemma
√ A.2,
 Ci > 1
and, by the paragraph containing (2.27), c∞ = z2∗ 1 − erf(z∗ / 2) . The last
equality in (2.29) follows by (A.12). The inequalities in (2.30) follow immediately
from (2.28), (2.29), and (A.13).
Proof of Proposition 2.13. By (2.25), (2.14), and (A.9),
(1
\
(1 − νb)
if 0 < ν ≤ 1,

bayes(ν) = 21
3
if 1 ≤ ν ≤ 3.
8 4 + b (ν − 1) − b(3 + ν)
Recalling now (2.26) and using the values b = 1 for ν ∈ (0, 21 ], b =
1
ν ∈ [ 12 , 1], and and b = 30
(17 − 2ν) for ν ∈ [1, 3], one obtains (2.32).

1
2ν

for

Details on Remark 2.14. The inequality B̂2 (ν) > B1 (ν) − 2 × 10−6 for all ν ∈
[1, 3], mentioned in that remark, can be verified, e.g., by issuing the Mathematica command Reduce[b 1/8 (4 + b^3 (nu - 1) - b (3 + nu)) - hB2[nu]
>= 2 10^(-6) && 1 <= nu <= 3 && 0 <= b <= 1], where hB2[nu] stands for
B̂2 (ν). \
This command then outputs False, which means that indeed B1 (ν) =
max b bayes(ν) = max b 18 (4 + b3 (ν − 1) − b(3 + ν)) < B̂2 (ν) + 2 × 10−6 .

0≤b≤1

0≤b≤1

Proof of Proposition 2.15. The first inequality in (2.33) holds by (2.21). Take
now any b ∈ (0, 1]. From (A.5), Lemma A.2, and inequality Sq (b) ≤ b, it follows
that
√
sk (b) ≤ b k
(3.16)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

21

for odd natural k. By (A.7), inequality (3.16) holds for even natural k as well,
and it trivially holds for k = 0. Using now the definition of B0 (m, d) in (2.21)
1
∈ (0, 1]
together with (2.14), (3.16), and Jensen’s inequality, noticing that 2√
ν
1
1
if ν ≥ 4 , and substituting 2√ν for b, one has
B0 (m, d) ≥ b E bayes(N, b) ≥

b
2

√ 
1 − bE N ≥

in the case when ν ≥ 14 .
It remains to consider the case when

1
4

B0 (m, d) ≥ B1 (ν) =

>ν≥
1
2

b
2

3
41 .

√

1 − b EN
√  0.125
= 2b 1 − b ν = √ ,
ν
Then, by (2.26) and (2.32),

0.125
(1 − ν) > √ ,
ν

which completes the proof of Proposition 2.15.
Proof of Theorems 2.4 and 2.16. The two inequalities in (2.18) are trivial. The
first, second, third, and fourth inequalities in (2.34) were already established as
the inequalities in (2.21), the second inequality in (2.26), the second inequality
in (2.28), and the first inequality in (2.30), respectively. The second asymptotic
equivalence in (2.34) follows immediately from (2.30) and (2.31).
So, in view of (2.13), it suffices to show that (2.19) holds and
? c
∞
B(m, d) . √ ,
ν

(3.17)

where, as usual, A . B means lim sup A/B ≤ 1.
In this proof, all the limit relations are stated for ν = m/d → ∞ and all
the other relations are stated under the condition that ν is large enough.
By (2.10), (2.7), (2.20), and (2.5),
R(LERM ; p, β) ≤

d
X



px |βx | P(Vxp,β 6= 0, sgn Vxp,β 6= sgn βx ) + P(Vxp,β = 0) .

x=1

(3.18)
Take now any b ∈ [0, 1] and k ∈ 0, ∞. In view of (2.16), Vkb equals −Vk−b in
distribution, and Vkb is stochastically greater than Vk−b (since b ≥ 0). So, by the
definition (2.14)–(2.15) of bayes(k, b),
bayes(k, b) = Q− (k, b) +

1
2

Q0 (k, b),

(3.19)

and Q0 (k, b) := P(Vkb = 0).

(3.20)

where
Q− (k, b) := P Vkb < 0



p
Recalling the definition of the random pairs (X1p , Y1p,β ), . . . , (Xm
, Ymp,β ) in
the paragraph containing (2.3) and (2.4), the definition of the random set Jxp

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

22

in (3.4), and the definition of the Yib ’s in Theorem 2.2, we see that, for any

p,β
[m]
p
J ∈
k , the conditional distribution of (Y

 i )i∈J given the event {Jx =
c
J} = {Xi = x ∀i ∈ J} ∪ {Xi 6= x ∀i ∈ J } is the same as the distribution of
(Y1βx , . . . , Ykβx ).
Therefore, if βx > 0 for some x ∈ [d], then, in view of (3.5), (2.20), and
(3.19),
P(Vxp,β 6= 0, sgn Vxp,β 6= sgn βx ) = P(Vxp,β < 0)
m
X
=
P(Vxp,β < 0, Nxp = k)
=

k=0
m
X

X

P Vxp,β < 0, Jxp = J



k=0 J∈([m])
k

=

m
X

X

P

k

m
X
X

Yip,β < 0, Jxp = J



i∈J

k=0 J∈([m])

=

X

P

k=0 J∈([m])

k
X


Yiβx < 0 P(Jxp = J)

i=1

k

=

m
k
m
X

X
X
P
Yiβx < 0 P(Nxp = k) =
Q− (k, |βx |) P(Nxp = k)
i=1
E Q− (Nxp , |βx |)

k=0

=

=

E bayes(Nxp , |βx |)

k=0
− 21

E Q0 (Nxp , |βx |).

Similarly, the latter expression, E bayes(Nxp , |βx |) − 12 E Q0 (Nxp , |βx |), for
P(Vxp,β 6= 0, sgn Vxp,β 6= sgn βx ) holds when βx < 0 as well. On the other hand,
it is similarly seen that
E Q0 (Nxp , |βx |) = P(Vxp,β = 0).
Thus, (3.18) yields
R(LERM ; p, β) ≤

d
X

px |βx | E bayes(Nxp , |βx |) +

x=1

d
1 X
px |βx | E Q0 (Nxp , |βx |).
2 x=1

In particular, in view of (2.13), this implies the second inequality in (2.19); the
first inequality there is trivial.
Now, to complete the proof of (2.19) and Theorem 2.16, it remains to verify
(3.17) and
d
X
?
sup
px |βx | E Q0 (Nxp , |βx |) = O(1/ν).
(3.21)
p,β x=1

Take any b ∈ (0, 1] and any natural k ≥ 3, so that, by (A.3) and (A.2),

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

23

q := qk ≥ 1 > 0. Note that sk (1) = 1. Hence, by (2.14) and (A.5),



bayes(k, b) = 12 1 − sk (b) = 21 sk (1) − sk (b) = 12 s0k (0) Sq (1) − Sq (b)
Z 1
Z 1
Z ∞
2
2
= 12 s0k (0)
(1 − u2 )q du ≤ 12 s0k (0)
e−qu du ≤ 21 s0k (0)
e−qu du
b
b
b
√ 
= Ak 1 − erf(b q ) , (3.22)
√
s0 (0) π

where Ak := k4 √q
√
z := b 2q one has

→

1
2

as k → ∞, by Lemma A.2 and (A.6). Therefore, for

√ 
λk z
λk
1 − erf(z/ 2 ) ≤ c∞ √
b bayes(k, b) ≤ √
k 2
k

(3.23)

by (2.1), where
λk := 2Ak

q

k
2q

→1

(3.24)

as k → ∞.
Take now any ε ∈ (0, 1). In view of (3.23) and the first part of Remark 2.3,
b bayes(k, b) ≤ √

A
k+1

(3.25)

for some real A > 0, all b ∈ [0, 1], and all k = 0, 1, . . . .
Since the r.v. Nxp has the binomial distribution with parameters m and px ,
one has the following well-known inequality:
P(Nxp ≤ (1 − ε)mpx ) ≤ e−ε

2

mpx /2

;

see e.g. [4, Exercise 2.9]; also, this inequality immediately follows from the more
general and precise results in [16, (1.3) or (2.31)] or [18, Theorem 7].
Therefore,
S01 :=

d
X

px E √

x=1

≤

d
X

1
Nxp + 1

I{Nxp ≤ (1 − ε)mpx }

px P(Nxp ≤ (1 − ε)mpx ) ≤

x=1

px e−ε

2

mpx /2

x=1
2
ε2

where aε :=

S02 :=

d
X

d
X

supu>0 ue−u =

px E √

x=1
d
X

1
Nxp + 1

2
eε2 ,

≤

d
X
x=1

aε

1
d
= aε , (3.26)
m
m

which depends only on ε. Also,

I{Nxp > (1 − ε)mpx }

1

d
X

√

px

1
p
≤
px p
≤
≤√
1−ε
(1 − ε)mpx + 1 x=1 (1 − ε)m
x=1

r

d
;
m

(3.27)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

24

the last inequality here is obtained
Pdusing the concavity of the square root function together with the condition x=1 px = 1. Thus, by (3.26) and (3.27),
d
X

px E √

x=1

1
Nxp

+1

= S01 + S02

1
≤
1−ε

r

d
m

(3.28)

(if m/d is large enough, depending on ε; recall the framed convention on page 21).
In view of (3.25),

S11 :=

d
X

px |βx | E bayes(Nxp , |βx |) I{Nxp > (1 − ε)mpx } I{px ≤ ε/d}

x=1
d
X

A
I{Nxp > (1 − ε)mpx } I{px ≤ ε/d}
p
N
+
1
x
x=1
√
d
d
X
X
px
A
p
px p
≤
I{px ≤ ε/d} ≤ A
I{px ≤ ε/d}
(1
−
ε)mp
+
1
(1
−
ε)m
x
x=1
x=1
r
p
r
d
X
ε/d
ε
d
p
=A
.
≤A
1−ε m
(1 − ε)m
x=1
≤

px E √

Next, taking into account (3.23), (3.24), and (3.27), one has

S12 :=

d
X

px |βx | E bayes(Nxp , |βx |) I{Nxp > (1 − ε)mpx } I{px > ε/d}

x=1

≤

d
X

px |βx | E bayes(Nxp , |βx |) I{Nxp > (1 − ε)mpx } I{Nxp > (1 − ε)εm/d}

x=1

≤

d
X
x=1

px (1 + ε)c∞ E √

1
Nxp + 1

I{Nxp > (1 − ε)mpx } = (1 + ε)c∞ S02
(1 + ε)c∞
≤ √
1−ε

r

d
.
m

So,

S1 :=

d
X

px |βx | E bayes(Nxp , |βx |) I{Nxp > (1 − ε)mpx } = S11 + S12

x=1

for some universal real constant A1 > 0.

r
√
(1 + A1 ε)c∞
d
√
≤
m
1−ε

(3.29)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

25

On the other hand, by (3.25) and (3.26),

S2 :=

d
X

px |βx | E bayes(Nxp , |βx |) I{Nxp ≤ (1 − ε)mpx }

x=1

≤ AS01

r
d
d
≤ Aaε ≤ ε
.
m
m

Combining this with (3.29), we conclude that
d
X

px |βx | E bayes(Nxp , |βx |)

x=1

r
√
d
(1 + A2 ε)c∞
√
= S1 + S2 ≤
m
1−ε

(3.30)

for some universal real constant A2 > 0. Thus, letting here ε be arbitrarily small
and recalling the definition of B(m, d) in (2.13), we complete the proof of the
asymptotic relation (3.17).
To complete the proof of Theorems 2.4 and 2.16, let us finally verify (3.21).
If k = 2j is even then, by (3.20),
 
2
2j 1
A3
A4
bQ0 (k, b) =
b(1 − b2 )j ≤ √
be−b k/2 ≤
j
j 4
k+1
k+1
for some universal real constants A3 > 0 and A4 > 0 and all b ∈ [0, 1]; since
Q0 (k, b) = 0 if k is odd, the above bound in fact holds for all k = 0, 1, . . . . So,
d
X

px |βx | E Q0 (Nxp , |βx |) ≤ A4

x=1

d
X
x=1

px E


1
1 d
≤
A
a
+
;
4
ε
Nxp + 1
1−ε m

the second inequality in the above display is obtained similarly to the inequality
in (3.28). Thus, (3.21) is verified, and the proof of Theorems 2.4 and 2.16 is
complete.
Proof of Theorem 2.1. Take any learning algorithm L ∈ Lrand . Take any b ∈
β
(0, 1] and then any ε ∈ (0, b) and any β ∈ {−b, b}[d] . Let Dβ and Zm
be as
β
ˆ β ≤ b. So,
ˆ β := ∆(L(Zm
in (2.22). Recall (2.6) and let ∆
, U ), Dβ ), so that ∆
ˆ β > ε} ≥ 1 (∆
ˆ β − ε), whence P(∆
ˆ β > ε) ≥ 1 (E ∆
ˆ β − ε). Therefore, by
I{∆
b−ε
b−ε
(2.9), Theorem 2.6, Proposition 2.8, and Jensen’s inequality,
max
β∈{−b,b}[d]

ˆ β > ε) ≥
P(∆

1
2d

X

ˆ β > ε)
P(∆

β∈{−b,b}[d]

1  1
≥
b − ε 2d

\
X
β∈{−b,b}

ˆ β − ε ≥ b bayes(ν, b) − ε .
E∆
b−ε
[d]


\
Take now
any ν∗ ∈ [3, ∞) and any real ν ≥ ν∗ . Then, by Lemma A.3 and

√
i +1 1/8
(A.13), bayes(ν, b) ≥ 21 1 − νi∗ν
ψb (ν) . Further, take any z ∈ (0, ν∗ ]
∗

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

26

√
√
and w ∈ (0, z), and then take b = z/ ν and ε = w/ ν, so that the conditions
b ∈ (0, 1] and ε ∈ (0, b) assumed in the beginning of this proof do hold. Then
 i + 1 1/8 erf(z/√2) i


1 z h
w 
ν∗
β
ˆ
1−
−
w
max P ∆ > √
≥
z−w 2
iν∗
exp{−z 2 /(6ν∗ )}
ν
β∈{−1,1}[d]
=: Plow (w, ν∗ , z).
1
331
320
√1
It remains to note that Plow ( √320
, 128
10 , 1000 ) > 0.238, Plow ( 320 , 3, 1000 ) > 0.227,
681
1
601
√ 1
Plow ( √ 1
, 128
, 3, 1000
) > 0.0159 >
10 , 1000 ) > 0.01563 > 64 , and Plow (
413/10

496/10

1
64 .

Acknowledgments
We are pleased to thank Peter Grünwald for bringing the result of [2] to our
attention, and the referees for carefully reading the paper and useful suggestions
on the presentation.
Appendix A: Identities and inequalities for binomial distributions:
details concerning the function bayes
Recall the definition of bayes in (2.14). Take any b ∈ [0, 1] and k ∈ 1, ∞. By
(2.15),
j  

1 X k 
sk (b) = k
(1 + b)k−i (1 − b)i − (1 − b)k−i (1 + b)i ,
2 i=0 i

Using identities (k − i)


k
i

j := jk := bk/2c.


= k k−1
and i ki = k
i

(A.1)
(A.2)


k−1
i−1

, we have


j 
X

k−1 
2k 0
sk (b) :=
(1 + b)k−i−1 (1 − b)i + (1 − b)k−i−1 (1 + b)i
k
i
i=0

j 
X

k−1
−
[(1 + b)k−i (1 − b)i−1 + (1 − b)k−i (1 + b)i−1 .
i−1
i=1
Making in the second sum the substitution i = r + 1, then replacing there r
back by i, and introducing
q := qk := k − j − 1,

(A.3)

we have


2k 0 . k − 1
= (1 + b)q (1 − b)j + (1 − b)q (1 + b)j = 2(1 − b2 )q ,
s (b)
k k
j

(A.4)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

27

which is non-increasing in b ∈ [0, 1]. So, the function sk is concave.
Moreover, it follows that
sk (b) =

s0k (0)Sq (b),

Z
where

b

Sq (b) :=

(1 − u2 )q du.

(A.5)

0

For all i ∈ 0, ∞, in view of (A.2), (A.3), and (A.4),
q2i+2 = q2i+1 = i

and s02i+2 (0) = s02i+1 (0)

(A.6)

and hence, by (A.5), one has the curious, and useful, identity
s2i+2 (b) = s2i+1 (b).

(A.7)

We also have
Lemma A.1. Take any b ∈ (0, 1). Then the function
{0, 1, 3, 5, . . . } 3 k 7→ bayes(k, b)

(A.8)

is strictly convex.
Proof. In view of (2.14), it is enough to show that the function {0, 1, 3, 5, . . . } 3
k 7→ sk (b) is strictly concave. By (A.1) and (A.2),
s0 (b) = 0,

s1 (b) = b,

s3 (b) =

1
2

(3b − b3 ) < 3s1 (b).

(A.9)

So, the restriction of the function in (A.8) to the set {0, 1, 3} is strictly concave.
It remains to show that the restriction of this function to the set {1, 3, 5, . . . }
is strictly concave. Take any i ∈ 0, ∞. We have to show that
g(b) := s̃i (b) + s̃i+2 (b) − 2s̃i+1 (b) < 0,
where
s̃i := s2i+1 .

(A.10)

By (A.5), s̃0α (b) = s̃0α (0)(1−b2 )α > 0; here and in the rest of this proof, α stands
for an arbitrary nonnegative integer. So, g 0 (b) has the same sign as
g 0 (b)
2(1 − b2 )(i + 2)(2i + 3) = −1 − 2(3 + 2i)w + (15 + 16i + 4i2 )w2 =: g1 (w)
s̃0i+1 (b)
(A.11)
where w := b2 . Since the function g1 is convex, with g1 (0) = −1 < 0 and
g1 (1) = 4(2 + 3i + i2 ) > 0, it follows that g1 (w) switches exactly once in sign,
from − to +, as w increases from 0 to 1. That is, g(b) switches exactly once, from
decreasing to increasing, as b increases from 0 to 1. Also, by (A.1) and (A.10),
s̃α (0) = 0 and s̃α (1) = 1, whence g(0) = 0 = g(1). Thus, indeed g(b) < 0 for all
b ∈ (0, 1).

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

Lemma A.2. For i ∈ 0, ∞, let
p
r
 
π(i + 1/2) 2i
π s02i+1 (0)
√
Ci :=
,
=
i
2 2i + 1
22i

28

(A.12)

the latter equality following by
p π(A.4) and (A.2).
Then Ci decreases from
2 to 1 as i increases from 0 to ∞, and for all
i ∈ 1, ∞
 i + 1 1/8
Ci <
.
(A.13)
i
Proof. In this proof, it is assumed that i ∈ 0, ∞. Let
2i + 2
Ci
> 1.
=p
Ci+1
(2i + 2)2 − 1
p
So, Ci indeed decreases in i. It is easy to check that C0 = π2 and Ci → C∞ := 1
as i → ∞.
It remains to verify inequality (A.13). Accordingly, assume through the end
of this proof that i ∈ 1, ∞. Then
ri :=

−1 + ri−8

.
1−

 96i4 + 384i3 + 560i2 + 352i + 81
1
=
> 0,
(i + 1)2
256i(i + 1)6 (i + 2)

which shows that

ri < 1 −

−1/8
1
,
(i + 1)2

whence
Ci = C∞

∞
Y
α=i

rα =

∞
Y

rα <

∞ 
Y

1−

α=i

α=i

=

−1/8
1
(α + 1)2

∞ 
Y
α . α + 1 −1/8  i + 1 1/8
=
,
α+1 α+2
i
α=i

which completes the proof of Lemma A.2.
Lemma A.3. Take any real κ ≥ 1 and any b ∈ [0, 1]. Then
\

bayes(κ, b) ≥ 12 1 − Ciκ ψb (κ) ,
where iκ := b κ−1
2 c, Ci as in (A.12), and
ψb (κ) := eb

2

/6

p
erf(b κ/2).

Proof. For brevity, let i := iκ = b κ−1
2 c and k := 2i + 1. Then i ∈ 0, ∞, k =
2i + 1 ≤ κ < 2i + 3 = k + 2, and so, by (2.25),
\
bayes(κ, b) =

k+2−κ
2

bayes(k, b) +

κ−k
2

bayes(k + 2, b).

(A.14)

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

29

In view of (A.2) and (A.3), jk = i = qk = q. It is well known and easily proved
(cf. e.g. [13]) that all mixtures of log-convex functions are log-convex. Therefore
Rb
2
2
and because the function q 7→ e−qu is log-convex, S̃q (b) := 0 e−qu du is log
convex in real q; that is, f (q) := ln S̃q (b) is convex in q. For readers’ convenience,
a quick and direct way to verify the convexity of f is to see that for any real
q1 , q2 and any t ∈ (0, 1) the inequality f ((1 − t)q1 + tq2 ) ≤ (1 − t)f (q1 ) +
Rb
tf (q2 ) can be rewritten as the instance of Hölder’s inequality 0 F1 (u)F2 (u) du ≤
Rb
Rb
2
2
( 0 F1 (u)p du)1/p ( 0 F2 (u)p̃ du)1/p̃ with F1 (u) := e−(1−t)q1 u , F2 (u) := e−tq2 u ,

S̃q+1/2 (b)S̃0 (b)
1
= f (q+1/2)−f (q)−f (1/2)+f (0) =
, and p̃ := 1t . So, ln
p := 1−t
S̃1/2 (b)S̃q (b)
R 1/2 0
[f (q + u) − f 0 (u)] du ≥ 0 for q ≥ 0, since f 0 (u) is increasing in u instead
0
of the last equality here, one can also use inequality
[8, (3.17.5)] with φ = f ,

h = x = q/2 + 1/4 and h0 = q/2 − 1/4 there . Recalling now (A.5) and using
the elementary inequality 1 − t ≤ e−t for real t, we have
S̃0 (b)
S̃1/2 (b)
p
√
b
π erf(b q + 1/2)
p
=
Rb
−u
2
q + 1/2
e 2 /2 du
0
(A.15)
p
√
π erf(b q + 1/2) b2 /6
p
≤
e
2
q + 1/2
r
r
p
π 1 b2 /6
π 1
√ e
√ ψb (k);
erf(b k/2) =
=
2 k
2 k
Rb
2
2
here we used the inequality g(b) := 0 e−u /2 du − be−b /6 > 0 for b > 0, which
2
2
follows because g(0) = 0 and g 0 (b) = e−b /6 (e−b /3 − (1 − b2 /3)) >0 for b > 0.
So, in view of (2.14), (A.5), and (A.12), bayes(k, b) ≥ 12 1−Ci ψb (k) . Replacing
here k by k + 2, one has


bayes(k + 2, b) ≥ 12 1 − Ci+1 ψb (k + 2) ≥ 12 1 − Ci ψb (k + 2) ;
Sq (b) ≤ S̃q (b) ≤ S̃q+1/2 (b)

the last inequality here follows because, by Lemma A.2, Ci decreases in i. Now
(A.14) yields
\

 1 1
bayes(κ, b) ≥ 12 − 12 Ci k+2−κ
ψb (k) + κ−k
2
2 ψb (k + 2) ≥ 2 − 2 Ci ψb (κ),
the latter inequality following by the concavity of ψb (u) in u ≥ 0. This completes
the proof of Lemma A.3.
Appendix B: Simplified form of cLB
m,d
Take any finite set X . Take then any hypothesis class H with VC(H ) = d.
Let now X˜ be any subset of X of cardinality d such that X˜ is shattered by

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

30

H . Clearly, for any learning algorithm L ∈ LX ;m,H we have
sup Rm (L, D) ≥
D∈DX

sup

Rm (L, D),

(B.1)

D∈DX ;X˜

where DX ;X˜ is the set of all distributions D ∈ DX with support contained
in the set X˜ × Y (and, recall, DX is the set of all distributions on X × Y ).
Next, any distribution D ∈ DX ;X˜ may be identified with the corresponding
distribution, say D̃, in DX˜ . Also, for any D ∈ DX ;X˜ , the value of Rm (L, D)
depends on L only through its restriction, say L̃, to (X˜ × Y )k — so that
Rm (L, D) = Rm (L̃, D̃). Moreover, we may identify the finite set X with the
set [N ] = {1, . . . , N } for some natural N ≥ d, and then without loss of generality
X˜ = [d] = {1, . . . , d}. Thus, for any finite set X and any hypothesis class H
with VC(H ) = d, it follows from (B.1) that
inf

sup Rm (L, D) ≥

L∈LX ;m,H D∈DX

inf

sup Rm (L̃, D̃).

(B.2)

L̃∈L[d];m,Y [d] D̃∈D[d]

The right-hand side (RHS) of (B.2)pdoes not depend on X or H , as long
as VC(H ) = d. So, by (1.10), cLB
m,d / m/d ≥ r.h.s. of (B.2). The reverse of
the latter inequality follows trivially fromp(1.10), since the set [d] is finite and
VC(Y [d] ) = d. We conclude that cLB
m,d / m/d = r.h.s. of (B.2). Thus, (2.2)
follows.
References
[1] Anthony, M. and Bartlett, P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge.
MR1741038 (2001b:68061)
[2] Audibert, J.-Y. (2009). Fast learning rates in statistical inference through
aggregation. Ann. Statist. 37 1591–1646.
[3] Berend, D. and Kontorovich, A. (2015). A finite sample analysis of
the Naive Bayes classifier. Journal of Machine Learning Research 16 1519–
1545.
[4] Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration
inequalities. Oxford University Press, Oxford A nonasymptotic theory of
independence, With a foreword by Michel Ledoux. MR3185193
[5] Devroye, L., Györfi, L. and Lugosi, G. (1996). A probabilistic theory of
pattern recognition. Applications of Mathematics (New York) 31. SpringerVerlag, New York. MR1383093
[6] Devroye, L. and Lugosi, G. (1995). Lower bounds in pattern recognition
and learning. Pattern Recognition 28 1011–1018.
[7] Ferguson, T. S. (1967). Mathematical statistics: A decision theoretic approach. Probability and Mathematical Statistics, Vol. 1. Academic Press,
New York-London. MR0215390
[8] Hardy, G. H., Littlewood, J. E. and Pólya, G. (1967). Inequalities.
Cambridge University Press, Cambridge Reprint of the 1952 edition.

A. Kontorovich and I. Pinelis/Exact Agnostic PAC Lower Bounds

31

[9] Haussler, D. (1992). Decision Theoretic Generalizations of the PAC
Model for Neural Net and Other Learning Applications. Inf. Comput. 100
78–150.
[10] Haussler, D. (1995). Sphere packing numbers for subsets of the Boolean
n-cube with bounded Vapnik-Chervonenkis dimension. J. Combin. Theory
Ser. A 69 217–232. MR1313896 (96f:52027)
[11] Kearns, M. J. and Schapire, R. E. (1994). Efficient distribution-free
learning of probabilistic concepts. J. Comput. Syst. Sci. 48 464–497.
[12] Kearns, M. J., Schapire, R. E. and Sellie, L. (1994). Toward Efficient
Agnostic Learning. Machine Learning 17 115-141.
[13] Kingman, J. F. C. (1961). A convexity property of positive matrices.
Quart. J. Math. Oxford Ser. (2) 12 283–284. MR0138632
[14] Kontorovich, A., Sabato, S. and Urner, R. (2016). Active NearestNeighbor Learning in Metric Spaces, NIPS 2016. CoRR abs/1605.06792.
[15] Long, P. M. (1999). The Complexity of Learning According to Two Models of a Drifting Environment. Mach. Learn. 37 337–354.
[16] Pinelis, I. (2016). Optimal binomial, Poisson, and normal left-tail domination for sums of nonnegative random variables. Electron. J. Probab. 21
1-19.
[17] Pinelis, I. F. (1991). Criterion for complete determinacy for concaveconvexlike games. Math. Notes 49 277–279.
[18] Pinelis, I. F. and Utev, S. A. (1989). Sharp exponential estimates for
sums of independent random variables. Theory Probab. Appl. 34 340–346.
MR1005745 (91a:60053)
[19] Shalev-Shwartz, S. and Ben-David, S. (2014). Understanding Machine
Learning: From Theory to Algorithms. Cambridge University Press.
[20] Simon, H. U. (1996). General bounds on the number of examples needed
for learning probabilistic concepts. J. Comput. System Sci. 52 239–254.
Sixth Annual Workshop on Computational Learning Theory (COLT)
(Santa Cruz, CA, 1993). MR1393992
[21] Sion, M. (1958). On general minimax theorems. Pacific J. Math. 8 171–
176. MR0097026 (20 ##3506)
[22] Talagrand, M. (1994). Sharper Bounds for Gaussian and Empirical Processes. Ann. Probab. 22 28–76.
[23] v. Neumann, J. (1928). Zur Theorie der Gesellschaftsspiele. Mathematische Annalen 100 295–320.
[24] Valiant, L. G. (1984). A Theory of the Learnable. Commun. ACM 27
1134-1142.
[25] Vapnik, V. N. and Červonenkis, A. J. (1971). The uniform convergence
of frequencies of the appearance of events to their probabilities. Teor. Verojatnost. i Primenen. 16 264–279. MR0288823 (44 ##6018)

