Boosted Density Estimation Remastered
arXiv:1803.08178v1 [cs.LG] 22 Mar 2018

Zac Cranko∗ Richard Nock†
firstname.lastname@data61.csiro.au

Abstract
There has recently been a steadily increase in the iterative approaches to boosted density estimation and sampling, usually proceeding by adding candidate “iterate” densities to a model that gets
more accurate with iterations. The relative accompanying burst of
formal convergence results has not yet changed a striking picture: all
results essentially pay the price of heavy assumptions on iterates, often
unrealistic or hard to check, and offer a blatant contrast with the
original boosting theory where such assumptions would be the weakest
possible. In this paper, we show that all that suffices to achieve boosting for density estimation is a weak learner in the original boosting
theory sense, that is, an oracle that supplies classifiers. We provide
converge rates that comply with boosting requirements, being better
and / or relying on substantially weaker assumptions than the state of
the art. One of our rates is to our knowledge the first to rely on not
just weak but also empirically testable assumptions. We show that the
model fit belongs to exponential families, and obtain in the course of
our results a variational characterization of f -divergences better than
f -GAN’s. Experimental results on several simulated problems display
significantly better results than AdaGAN during early boosting rounds,
in particular for mode capture, and using architectures less than the
fifth’s of AdaGAN’s size.
∗
†

Data61 & The Australian National University
Data61, The Australian National University & The University of Sydney

1

1

Introduction

Learning a distribution Q to approximate a true distribution P over a space
X entails potentially two difficulties: Firstly, ensuring formally that Q is close
to P . That is, guaranteeing
I(P, Q) ≤ C,

(1)

where I is any suitable form of divergence, and C can take a variety of forms.
Secondly, devising an easy way to generate samples from Q. There is no
approach to date that satisfies both objectives for both C sufficiently small
with reasonable assumptions and a sampling scheme sufficiently efficiently
in the worst cases. Recent approaches, formal and/or experimental, have
promoted the idea that Q can be learned in an iterative way using density
iterates obtained from an oracle, and analyzed convergence alongside the
original boosting theory [Grover and Ermon, 2018, Guo et al., 2016, Locatello
et al., 2017, Miller et al., 2017, Tolstikhin et al., 2017, and references therein].
Experimentally, successful applications have essentially be framed in the
context of variational inference [Guo et al., 2016, Locatello et al., 2017,
Miller et al., 2017] or Generative Adversarial Networks (GANs) [Tolstikhin
et al., 2017]. To our knowledge, there is no such black box method whose
convergence has been proven towards the optimum and with realistic and/or
easily checkable assumptions. For example, the strongest of the convergence
results, which exhibit geometric rates, assumes that the iterates are close to
the optimum sought [Tolstikhin et al., 2017]. All previous results attaining at
least sublinear convergence rates — that represent the main body of results in
the field — also make strong assumptions about the parameters and models
at hand. It is therefore not just about obtaining efficient black boxes: the
question as to whether substantial convergence holds under some sufficiently
weak assumptions is also yet to be framed and answered.
Historically, when the statistical and computational requirements of supervised learning were still a challenge, the boosting approach to PAC learning
[Kearns, 1988, Valiant, 1984], and its first formal proof [Schapire, 1990] elegantly showed that all one needs is in fact a weak learner, returning classifiers
with the sole constraint to be slightly different than the unbiased coin. In
a sense, any weaker than this requirement would allow just plain random
guessing and would thus not be qualifiable as “learning”.
Our main formal contribution shows that the same weak learners can be
used to solve the density learning problem in the boosting framework — that
2

is, we built Q using classifiers. We attain convergence rates that compete with
sublinear rates, with assumptions far weaker than those of previous results.
Modulo an additional weak assumption on the distribution of errors, that
we call weak dominance, we reach geometric convergence rates that compete
with the best known without assuming anything about the relationship of the
iterates to the optimum P , nor about the location of the optimum [Guélat
and Marcotte, 1986]. In the course of this contribution, we provide additional
results of independent interest, including a better characterization of the
variational f -GANs objective of Nowozin et al. [2016] and a proof that the Q
we learn belongs to exponential families, with a sufficient statistics defined by
the classifiers’ mappings. Hence, we learn distributions whose analytical form
is well studied and simple but parameterized on a statistical manifold which
can be as complex as e.g. permitted by deep learning.
We complete our contribution with an experimental validation of our
results, including the implementation of a sampler for Q fit to small to
moderate domains that we test on simulated problems. Our results display
the ability to rapidly capture modes through iterations — which is a key
problem for generative approaches [Tolstikhin et al., 2017]. A comparison
with AdaGAN displays that we converge much faster early to good solution,
with architectures that represent only the fifth’s of AdaGAN’s size.
The rest of this paper is as follows. In §2, we summarize related work
in the area. In §3, we provide preliminary definitions and results. In §4, we
develop our theoretical results, and in §5 we present experiments. We discuss
our findings in §6. A final section (§7) concludes the paper. This paper is
self-contained but to keep it readable, all formal proofs are deferred to the
appendices, starting p. 27.

2

Related work

In learning a density, it is remarkable that most previous approaches [Grover
and Ermon, 2018, Guo et al., 2016, Li and Barron, 2000, Miller et al., 2017,
Rosset and Segal, 2002, Tolstikhin et al., 2017, Zhang, 2003, and references
therein] have investigated a single update rule, not unlike Frank–Wolfe optimisation:
(∀αt ∈ [0, 1]) Qt+1 = f (αt g(ct ) + (1 − αt )g(Qt )),
3

(2)

where g is in general (but not always) the identity. Grover and Ermon [2018]
is one (recent) rare exception to (2) wherein alternative choices are explored.
Apart from the fact that they would rely on gradient-based optimisation in
the general case, few results are accompanied by convergence proofs, and even
less display convergence rates, which are mandatory in a boosting setting
[Guo et al., 2016, Li and Barron, 2000, Rosset and Segal, 2002, Tolstikhin
et al., 2017, Zhang, 2003].
Two categories of convergence results results prevail: bounds of the form
I(P, QT ) ≤ inf Q I(P, Q) + J/T for J > 0, as pioneered by Li and Barron
[2000]; and tighter geometric convergence bounds of the type I(P, QT ) ≤
(1 − J)T I(P, Q0 ) for J ∈ [0, 1] [e.g. Tolstikhin et al., 2017]. The quantity J
can take a variety of forms depending on the domain’s parameters. Several
approaches in (2) and J employ parameters that are not explicitly computable:
they can be the solution to alternative optimization problems [Guo et al.,
2016, Naito and Eguchi, 2013, Rosset and Segal, 2002, Zhang, 2003] (and
therefore require additional algorithmic machinery which, if not carefully
designed, may break convergence guarantees [Miller et al., 2017]), or they
simply may not be available in closed form in general [Tolstikhin et al., 2017,
Theorems 1, 2].
To establish convergence and/or bound convergence by a rate, all approaches necessarily make structural assumptions or approximations on the
parameters involved in (2) or (1). These can be on the (local) variation of I
[Guo et al., 2016, Naito and Eguchi, 2013, Zhang, 2003]; the true density P
or the updates Qt [Grover and Ermon, 2018, Guo et al., 2016, Li and Barron,
2000]; the mixing parameter αt [Miller et al., 2017, Tolstikhin et al., 2017]; the
weak learners ct [Grover and Ermon, 2018, Rosset and Segal, 2002, Tolstikhin
et al., 2017, Zhang, 2003]; the previous updates, (cj )j≤t ,[Rosset and Segal,
2002]; and so on. The price to get the best geometric convergence bounds
is in fact heavy considering that the update ct is in all cases required to be
close to the optimal one [Tolstikhin et al., 2017, Corollaries 2, 3].
To our knowledge, no previous work relaxes these assumptions yet still
achieves the best possible convergence rates — which would indeed look like
weak learning. It must be kept in mind, however, that for many of these
works, the objective is also to get an efficient black box for sampling from P .
With regards to this objective, boosting approaches like those of Miller et al.
[2017], Tolstikhin et al. [2017] stand out, Tolstikhin et al. [2017] certainly
being the closest to ours in their formal setting.

4

3

Preliminaries

In the sequel (X , M̃ ) is a measure space. Unnormalised measures on X are
usually indicated by decorated capital letters, M̃ , and probability measures
by capital letters without decoration, P . Without loss of generality we assume
all measures are absolutely continuous with respect to M̃ .
To an extended real function, f , we associate another extended real
·
function, f ∗ , called the Fenchel conjugate with f ∗ (x∗ ) = supx∈X hx∗ , xi − f (x).
If f is convex, proper, and lower semi-continuous, f = (f ∗ )∗ . If f is strictly
convex and differentiable on int(dom f ) then (f ∗ )0 = (f 0 )−1 .
An important tool of ours are information theory’s standard divergence
measures, f -divergences [Ali and Silvey, 1966, Csiszár, 1967]. The f -divergence
of P from Q is

Z 
dP
·
If (P, Q) = f
dQ,
dQ
where f : R → (−∞, +∞] is assumed convex and lower semi-continuous.
Common divergence measures such as Kullback–Liebler (KL) and total variation can easily be shown to be members of this family by picking f accordingly
[Reid and Williamson, 2011]. Several examples of these are listed in Table 1.
A great number of machine learning problems admit an informationtheoretic formulation that can be stated in terms of an information divergence
minimisation problem of the form
minimise

I(P, Q) subject to

Q ∈ Q,

(D)

where Q is a family of candidate distributions. Using some f -divergence as
I is convenient for machine learning as every f -divergence has a variational
representation via the Fenchel conjugate:


If (P, Q) =
sup
EP u − EQ f ∗ ◦ u .
(3)
u∈(dom f ∗ )X

The variational representation (3) has been shown to be convenient way
to estimate an f -divergence [Nguyen et al., 2010], but more recently it has
appeared in the form of Generative Adversarial Networks (GAN’s) [Goodfellow
et al., 2014, Nowozin et al., 2016] that solve (D) via a reparameterised
variational representation.
5

It is a common result [Nguyen et al., 2010, Grover and Ermon, 2018] that
the supremum in (3) is achieved for f 0 ◦ dP/dQ. And so if one is interested in
finding the function dP/dQ, a sensible thing to do may be to reparameterise
(3) and find it directly. Considering the corresponding minimisation problem
to (3), we define the reparameterised variational problem:
·

minimise J(u) = EQ f ∗ ◦ f 0 ◦ u − EP f 0 ◦ u subject to

u ∈ F (V)

This reparameterisation can be justified in the case where f is strictly convex,
as this makes f 0 a bijection. However, what one loses with this reparameterisation is convexity—that is, J is not necessarily convex in u. When F is the
set of continuous real functions on X the solution to (V) easily follows [cf.
Nowozin et al., 2016]. However when F is a more constrained class, a stronger
result is necessary. Assume F belongs to a normed space, (F, | · |). Let F∗
be its continuous dual. The Fréchet normal cone (also called prenormal cone)
of F ⊆ F at u ∈ F is
)
(
hu∗ , v − ui
·
∗
∗
≤0 .
NF (u) = u ∈ F : lim sup
F ⊇(v)→u |v − u|
When F is convex, NF (u) is the ordinary normal cone.
Lemma 4. Assume f : R+ → R+ is strictly convex and twice differentiable,
and F is a normed space of functions X → int(dom f ). Let F ⊆ F and
ū ∈ arg minu∈F J(u). If J is finite on a neighbourhood of ū, then ū ∈
dP/dQ − NF (ū). If, in addition, F is convex with dP/dQ ∈ int F, then
ū = dP/dQ.
The set NF (ū) can be thought of as containing a direction v that pulls
dP/dQ to the constrained minimiser ū. This is illustrated in Figure 2.
We can further reparameterize (V) in the context of machine learning to
take into account three fundamental sets of supervised learning: the families of density ratios, binary conditional distributions, and binary classifiers,
respectively
·

·

R(X ) = {d : X → (0, ∞)}, D(X ) = {D : X → (0, 1)},
·
C(X ) = {c : X → R}.
While it might seem like there are certain inclusions here (for example D(X ) ⊆
R(X ) ⊆ C(X )), these categories of functions really are distinct objects when
6

F
dP
dQ

−v
ū

NF (ū) + ū

Figure 2: Illustration of Lemma 4 wherein there exists v ∈ NF (ū) which pulls
the unconstrained minimiser, dP/dQ, onto the constrained minimiser, ū.
exp ◦
C(X )

R(X )

σ◦

D(X )

f 0◦

int(dom f ∗ )X

ϕ◦

Figure 4: Classification function classes and isomorphisms useful for reparameterising the variational problem (V).
thought of with respect to their corresponding binary classification decision
rules (listed in Table 3). It is easy to see that these sets are all isomorphic
with the commonly used connections
·

ϕ(D) =

1
D
·
, σ(c) =
, (ϕ ◦ σ) = exp,
1−D
1 + exp(−c)

which are illustrated in Figure 4. It is worth noting the selection of isomorphisms here is not unique and can be designed from principles involving loss
functions [Reid and Williamson, 2010]. The careful reader may notice that f 0
maps into int(dom f ∗ ) rather than dom(f ∗ ). However the distinction is not
important since the difference relies on a set of measure zero.
Example 1 (Neural Classifier). When a function d is modeled using a neural
network classifier D ∈ C(X ), d can be efficiently calculated by substituting the
softmax layer with


exp c(x)
exp c(x) = ϕ
= ϕ ◦ D(x) = d(x),
1 − exp c(x)
where c(x) is the neural network output at x ∈ X . This is just the arrow
C(X ) → R(X ) in Figure 4.
7

Example 2 shows that the reparameterised variational problem (3) together
with the isomorphisms in Figure 4 give a simple, principled choice for the
‘output activation function’, gf , of Nowozin et al. [2016].
Example 2 (f -GAN). The GAN divergence (Table 1) is expressed in terms
of a function D ∈ D(X ). It can derived as a special case of (V) as follows


GAN(P, Q) = sup EP (f 0 ◦ ϕ) ◦ D − EQ (f ∗ ◦ f 0 ◦ ϕ) ◦ D
D∈D(X )


= sup EP log(D) + EQ log(1 − D) ,
D∈D(X )
·

where f (t) = t log t − (1 + t) log(1 + t). This is the main result of Nowozin
et al. [2016].

4

Boosted Density Estimation

For multiplicative discriminative boosting we find distributions Qt for t =
1, 2, ... over the space X with the following density:
t
Y
1
dαi i dQ0 ,
dQt = R Qt
αi
dQ
d
0 i=1
i=1 i
·

(4)

where (αt ) ⊆ [0, 1] are the step sizes (for reasons that will be clear shortly),
and dt : X → R+ are some positive functions. The previous density can be
expressed recursively as follows:
Z
1
·
αt
dQ̃t = dt · dQ̃t−1 , Qt = Q̃t , Zt = dQ̃t .
(5)
Zt
Proposition 8. The normalisation factors can be written recursively with
Zt = Zt−1 · EQt−1 dαt t .
The updates dt are chosen by taking the minimiser of the the variational
problem (V). To make explicit the dependence of Qt on αt we will sometimes
·
·
write dQ̃t |αt = dαt t dQ̃t−1 and dQt |αt = Z1t dQ̃t |αt .
Proposition 9. Let c1 , . . . , ct ∈ C(X ) be a sequence of binary classifiers.
Then The distribution Qt is an exponential family distribution with natural
·
·
parameter α = (α1 , . . . , αt ) and sufficient statistic c(x) = (c1 (x), . . . , ct (x)).
8

The sufficient statistic of our distributions are classifiers that would hence
be learned, along with the appropriate fitting of natural parameters. As
explained in the proof, the representation may not be minimal; however,
without further constraints on α, the exponential family is regular [BarndorffNielsen, 1978]. In the remaining of the Section, we show how to learn the
classifiers from c(x) and fit the natural parameters α from (observed) data to
ensure a convergence Qt →t P that fits to the boosting framework.

4.1

General convergence results of Qt to P

Since Qt is an exponential family from Proposition 9, we measure the divergence between P and Qt using the KL divergence (Table 1), which is the
canonical divergence of exponential families [Amari and Nagaoka, 2000]. From
now on, we consider that F ( R(X ). Notice that we can rewrite any solution
to (V) as
dt =

dP
· εt
dQt−1

(6)

with
·

R(X ) 3 εt = 1 −

dQt−1
· vt
dP

for some vt ∈ NF (dt )

(7)

We call εt the error term. The main interest in representing dt via εt instead
of via vt is that it allows us to bound the KL divergence of P from Qt in a
convenient way.
Theorem 6. For any αt ∈ [0, 1] and εt ∈ [0, +∞)X , letting Qt as in (4) and
dt as in (6), we have:
KL(P, Qt |αt ) ≤ (1 − αt ) KL(P, Qt−1 ) + αt (log EP εt − EP log εt ).

(8)

We emphasize the fact that Theorem 6 holds not just for the optimal
choices of εt in (7), but in fact for all possible functions in [0, +∞)X , covering
essentially all ways — and thus applying to all related algorithms — for
computing dQt as in (4).
Remark 3. • Managing an error term uniform, εt ≡ k > 0 a constant a. e.,
guarantees a geometric convergence for the KL divergence:
KL(P, Qt |αt ) ≤ (1 − αt ) KL(P, Qt−1 ),
9

(9)

since the Jensen remainder log EP εt − EP log εt = log k − log k = 0. We get a
result significantly stronger than Grover and Ermon [2018, Theorem 2], who
just get the non-increase of the KL divergence under similar conditions.
• If, in addition to having uniform error, we fix in this case αt = 1, then
it is not hard to check from (4) and (5) that we get Qt = P . This is also
implied from (9) as in this case it yields KL(P, Qt |αt ) = 0, the KL divergence
being non negative and taking its minimum at Qt = P .
There is a way to express the update (4) and (8) in a way that is more
reminiscent to Frank–Wolfe type optimisation as highlighted in Section 2.
Since εt takes on positive values, we can see it as a density ratio involving a
(not necessarily normalised) measure R̃t , as
·

dR̃t = εt · dP.

(10)

It is consistent to define
·

Rt = R

1
· R̃t ,
dR̃t

(11)

the probability measure built from R̃t . Thus, in the case where dt is an
inexact solution to the variational problem, the update (5) becomes

αt
dRt
dQt ∝
dQt−1 = (dRt )αt · (dQt−1 )1−αt ,
dQt−1
which bears in disguise the Frank–Wolfe type update for iterate Rt . We
insist on the fact that this iterate is unknown in general — the parallel
with Frank–Wolfe is therefore more superficial than for (2). Introducing the
measure R̃t allows us to lend some interpretation to Theorem 6 in terms of of
its normalisation, Rt .
Corollary 7. For any αt ∈ [0, 1] and εt ∈ [0, +∞)X , letting dQt as in (4),
dt as in (6) and dRt from (10) and (11), if Rt satisfies
KL(P, Rt ) ≤ γ KL(P, Qt−1 )

(12)

KL(P, Qt |αt ) ≤ (1 − αt (1 − γ)) KL(P, Qt−1 ).

(13)

for γ ∈ [0, 1], then

10

Algorithm 1 AdaBoDE
“‘”’
Input: distributions P, Q0 , natural T ;
for t = 1 to T do
ct ← WeakLearn(P, Qt−1 );
Pick νQt−1 as in (15) and αt as



1 + νQt−1
1
αt ← min 1, ? log
;
2ct
1 − νQt−1

(14)

·

Pick Qt as in (4) with dt = exp ◦ct ;
end for
Return: QT

We obtain the same geometric convergence result as in the best result of
Tolstikhin et al. [2017, Corollary 2] for an update Qt which is not a convex
mixture, which, to our knowledge, is a new result. Corollary 7 is restricted to
the KL divergence but we do not need the technical domination assumption
of Qt with respect to P that Tolstikhin et al. [2017, Corollary 2] requires.
From the standpoint of weak versus strong learning, Tolstikhin et al. [2017,
Corollary 2] requires an condition similar to (12) — iterate Rt has to be close
enough to the optimal iterate with respect to P , while we assume that it
is close enough to P . We insist on the fact that such assumptions are very
strong. It is the objective of the following sections to relax them to a setting
compatible with boosting.

4.2

Convergence under weak learning assumptions

In the previous Section, we have established two basic convergence results
that compete with or beat the state of the art and rely on similar, strong
assumptions [Grover and Ermon, 2018, Tolstikhin et al., 2017]. We now see
how to relax those assumptions in the context of boosting.
Let us define the two expected edges of ct [cf. Nock and Nielsen, 2008]:
·

νQt−1 =

1
EQt−1 [−ct ],
c?t

·

and µP =

1
EP [ct ].
c?t

(15)

Classical boosting results rely on assumption on such edges for different
kinds of ct [Freund and Schapire, 1997, Schapire, 1990, Schapire and Singer,
11

·

1999] and the implicit and weak assumption, that we also make, that c?t =
maxt ess sup |ct |  ∞, that is, the classifiers have bounded confidence. By
definition, νQt−1 , µP ∈ [−1, 1]. The difference of sign of ct is due to the
decision rule for a binary classifier (Table 3), whereby ct (x) ≥ 0 reflects that
ct classifies x ∈ X as originating from P rather than Qt−1 , and vice versa for
−ct (x).
Assumption 1 (Weak Learning Assumption).
(∃γP , γQ ∈ (0, 1])

µP ≥ γP , νQt−1 ≥ γQ .

(WLA)

The Weak Learning Assumption is in effect a separation condition of P
and Qt−1 . That is, the decision boundary associated with ct correctly divides
most of the mass of P and most of the mass of Q. This is illustrated in
Figure 5. Note that if Qt−1 has converged to P , the weak learning assumption
cannot hold. This is reasonable since as Qt−1 → P it becomes harder to build
a classifier to tell them apart.
Define WeakLearn the weak learner which, taking P and Qt−1 as input,
delivers ct satisfying the conditions of WLA. In the boosting theory, which
involves a supervised learning problem, there is one condition instead of two
as in WLA: given a distribution D over X × {−1, +1}, we rather require from
the weak learner, WeakLearn∗ , that
(∃γ ∈ (0, 1])

1
ED y · ct ≥ γ,
c?t

where y denotes the class, mapping X → {−1, +1}. While is seems rather
intuitive that we can craft WeakLearn∗ from WeakLearn, it is perhaps
less intuitive as to whether the same can be done for the reverse direction.
We now show that it is indeed the case and WLA and WLA∗ are in fact
equivalent.
Lemma 10. Suppose γP = γQ = γ in WLA and WLA∗ , without loss of
generality. Then there exists WeakLearn satisfying WLA iff there exists
WeakLearn∗ satisfying WLA∗ .
Because there are two regimes for αt , we define two boosting regimes,
a high boosting regime, αt = 1 (“clamped”), and a regular boosting regime,
αt < 1 (“not clamped”). We show two rates of decrease for the KL divergence,
one for each regime.
12

Kullback–Liebler
Rev. Kullback–Liebler
Hellinger
Pearson
GAN

If

f (t)

f ∗ (t∗ )

f 0 (t)

(f ∗ ◦ f 0 )(t)

KL
rKL
χ2
GAN

t log t
√|t − 1| 2
( t − 1)
(t − 1)2
t log t − (t + 1) log(t + 1)

exp(t∗ − 1)
− log(−t∗ ) − 1
3(t∗ − 1)−1 − 1
t∗ (4 + t∗ )/4
− log(1 − exp(t∗ ))

log t + 1
−1/t
1 − 1/t
2(t − 1)
− log(t) − log(t + 1)

t
log
√ t−1
t−1
t2 − 1
log(1 + t)

Table 1: Some common f -divergences and their variational components.

Collection
Decision rule

R(X )
d≥1

D(X )
D ≥1−D

C(X )
c≥0

Table 3: Summary Binary classification decision rules for the families of
classification function R(X ), D(X ), and C(X ).

1
c?
t

· ct
P
µP

− c1? · ct
t

1
c?
t

· ct
P

Qt−1
νQt−1

µP

− c1? · ct
t

Qt−1
νQt−1

(a) The WLA is satisfied since µP and νQt−1 are (b) The WLA is violated since νQt−1 is negative.
postive.

Figure 5: Illustration of WLA in one dimension with a classifier ct and its
decision rule (indicated by the dashed grey line). The red (resp. blue) area is
the area under the ct /c?t · dP (resp. −ct /c?t · dQ) line, that is, µP (resp. νQt−1 ).

13

Convergence in the regular boosting regime The WLA alone is sufficient to guarantee a significant decrease of the KL divergence of P from Qt−1
at each boosting iteration:
Theorem 19. In the regular boosting regime and under WLA,


1 + νQt−1
µP
log
.
KL(P, Qt |αt ) ≤ KL(P, Qt−1 ) −
4
1 − νQt−1
The proof of the theorem uses a simple reverse of Jensen’s inequality
which may be of independent interest. Remark that even when we require
that ct meet WLA, the decrease of the KL divergence uses its actual values
for µP , νQt−1 , which can yield a substantially larger KL decrease.
Convergence in the high boosting regime This is where things get
interesting; when αt is clamped to 1, the decrease in the KL divergence at
each iteration is guaranteed to be of order c?t , and can even be significantly
larger depending on the actual values of νQt−1 and νc?t , defined as
·

νc?t =

exp(2c?t ) − 1
∈ (0, 1),
exp(2c?t ) + 1

(16)

Because αt = 1, it means νQt−1 ≥ νc?t , so let us write νQt−1 = (1 + δt−1 )νc?t for
some δt−1 ≥ 0.
Theorem 21. In the high boosting regime,
KL(P, Qt |αt ) ≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·

!
1
δt−1
+
.
2 1 − νc2?t

Note that Theorem 21 doese not assume WLA.

4.3

Rates for Boosting

A boosting algorithm would ensure, for any given error % > 0, that there exists
a number of iterations T for which we do have KL(P, QT ) ≤ %, where T is required to be polynomial in all relevant parameters: 1/γP , 1/γQ , c?t , KL(P, Q0 ).
Notice that we have to put KL(P, Q0 ) in the complexity requirement since it
can be arbitrarily large compared to the other parameters.

14

Theorem 22. Suppose WLA holds at each iteration. Then using Qt as in
(4) and αt as in (14), we are guaranteed that KL(P, QT ) ≤ % after a number
of iterations T satisfying:
T ≥2·

KL(P, Q0 ) − %
.
γP γQ

There is more to boosting: the question naturally arises as to whether
faster convergence is possible. A simple observation allows to conclude that
it should require more than just WLA. Denote
·

µε t =

1
· EP log εt
c?t

the normalized expected log-density estimation error. Then we have µP =
(1/c?t ) · KL(P, Qt−1 ) + µεt , so controlling µP does not give substantial leverage
on KL(P, Qt ) because of the unknown µεt . We show that an additional weak
assumption on µεt is all that is needed with WLA, to obtain convergence rates
that compete with Tolstikhin et al. [2017, Lemma 2] but using much weaker
assumptions. We call this assumption the Weak Dominance Assumption
(WDA).
Assumption 2 (Weak Dominance Assumption).
(∃Γε > 0)(∀t ≥ 1) µεt ≥ −Γε

(WDA)

The WDA takes its name from the observation that we have


dP
ct = log dt = log
· εt and |ct | ≤ c?t ,
dQt−1
so by ensuring that εt is essentially going to be non-zero a. e. WDA states
that nowhere in the support do we have dQt−1 . negligible against dP . This
also looks like a weak finite form of absolute continuity of dP with respect
to dQt−1 , which is not unreminiscent of the boundedness condition on the
log-density ratio of Li and Barron [2000, Theorem 1]. Provided WLA and
WDA hold, we are able to show geometric boosting convergence rates.
Theorem 23. Suppose WLA and WDA hold at each boosting iteration. Then
we get after T boosting iterations:

T
min{2, γQ /c?t }γP
KL(P, QT ) ≤ 1 −
· KL(P, Q0 ).
2(1 + Γε )
15

Algorithm 2 AdaBoDE.EST
Input: distributions P, Q0 , T ∈ N∗ , 0 < δ ≤ 1;
for t = 1 to T do
(ct , ν̂Qt−1 ) ← WeakLearn(P, Qt−1 , δ, T );
n
 1+ν̂
o
Q
αt ← min 1, 2c1? log 1−ν̂Qt−1
;
t

t−1

·

Pick Qt as in (4) with dt = exp(ct );
end for
Return: QT
Hence, we get a boosting algorithm which guarantees KL(P, QT ) ≤ % after
a number of iterations T which is now logarithmic in relevant parameters:
·
T ≥ (1/ log K)·log(KL(P, Q0 )/%), where K = 1/(1−(min{2, γQ /c?t }γP /(2(1+
Γε )))).

4.4

Boosting with Estimates

In practice, we do not have access to P and we rather sample from Q.
We thus assume the possibility to sample1 P and Q. to compute all needed
estimates of µP and νQ. . So let us assume that the weak learner has access
to a sampler of P and a sampler of Q. , “Sampl”. Sampl takes as input a
distribution and a natural m; it samples from the distribution and returns
an i.i.d. sample of size m. It does so separately for P and Q, with separate
sizes mP and mQ for the respective samples. The full Algorithm 2 is very
similar to Algorithm 1 if we except the fact that the weak learner also returns
an estimate for νQt−1 . To analyze Algorithm 2 requires however more than
just the boosting material developed so far, since nothing guarantees that
estimates of µP and νQ. meeting WLA would imply µP and νQ. meeting WLA
as well. We therefore replace WLA by one which relies on estimates computed
over large enough samples. We call it the Empirical Weak Learner Assumption
(EWLA). It involves two additional parameters, κ? = νc?t (1 − νc?t )/2 (> 0),
where νc?t , which depends only on c?t , is defined in (16), and some 0 < δ ≤ 1.
Assumption 3 (Empirical Weak Learner Assumption). There exists γP , γQ ∈
1

We could also assume the availability of training samples, in particular for P as usually
carried out.

16

(0, 1] such that the following holds: at each iteration t = 1, 2, ..., T , WeakLearn estimates µ̂P and ν̂Qt−1 respectively from
Sampl(P, mP )

and

Sampl(Qt−1 , mQ )

with mP , mQ satisfying
mP ≥

1
(κ? γP )2

log

4T
δ

mQ ≥

and

1
(κ? γQ )2

log

4T
,
δ

(EWLA(δ, T ))

and returns, along with ν̂Qt−1 , ct satisfying µ̂P ≥ γP and ν̂Qt−1 ≥ γQ .
The weak learner thus also take as input δ and T , as displayed in Algorithm 2. We emphasize the fact that EWLA(δ, T ) is just assuming the ability
for WeakLearn to have i.i.d. samples from P and Q and get a classifier
ct that empirically satisfies WLA. Since we still focus on the decrease of
KL(P, Q. ), one might expect this to weaken our results, which is indeed the
case, but we can show that only constants are slightly affected, thereby not
changing significantly convergence rates. We provide in one theorem the
reframing of both Theorem 19 and Theorem 21. In the same way as we did for
Theorem 21, whenever we are in the clamped regime for αt , we let δ̂t−1 ≥ 0
be defined from ν̂Qt−1 = (1 + δ̂t−1 )νc?t .
Theorem 27. Suppose EWLA(δ, T ) holds. Then with probability of at least
1 − δ,
(∀t = 1, 2, ..., T )

KL(P, Qt ) ≤ KL(P, Qt−1 ) − ∆t ,

where

 1+ν̂

Qt−1
µ̂P

 16 log 1−ν̂Q
t−1
·

∆t = µ̂ c?
P t
2

 2 + νc?t · 41 +

5

in the non-clamped regime,
δ̂t−1
1−νc2?


otherwise.

t

Experiments
·

Our experiments take palce X = R2 . We use the following simple neural
network classifier
tanh

tanh

dense

dense

σ

Dt : X −−−→ R10 −−−→ R →
− (0, 1),
17

(17)

which we transform into a density ratio, dt , by substituting the sigmoid
activation with an exponential function (cf. §3). To generate samples from
Qt−1 for training we use random walk Metropolis–Hastings. The network Dt
is trained with 10k samples each from P and Qt−1 using Nesterov’s accelerated
gradient descent η = 0.01 for 600 epochs with cross-entropy loss. One quarter
of the pooled P and Qt−1 samples are reserved for a test set, which we use
for early stopping.

5.1

Metrics

To compare our results with Tolstikhin et al. [2017] we compute their coverage
·
metric2 : Cκ (P, Q) = P (lev>β dQ), where Q(lev>β dQ) = κ, and κ ∈ [0, 1].
That is, we first find a set where most of the mass of Q lies, lev>β dQ, then
look at how much of the mass of P resides there. In addition to Cκ we also
compute the negative log-likelihod (NLL) EP [− log dQ] and KL divergence.

5.2

Convergence

At each iteration t we train a new binary classifier ct ; we use this classifier to
push Qt−1 towards P . As Qt gets closer to P it becomes harder and harder
to build a good classifier to tell them apart. This is easy to see in Figure 7.
As the KL divergence decrease with t, Figure 7b, the minimal cross entropy
we’re able to achieve over the course of training increases Figure 7a.
Dually we can interpret convergence in terms of the difficulty of constructing the weak lerner from §4. In Figure 7b we plot the quantites µP
and νQt . At the beginning of each iteration of training either µP or νQt is
negative, indicating that the classifier we’re learning does not yet satisfy
WLA, by the end of training both are positive. Furthermore, as with training
iterations t the maximal value we’re able to achieve in min{µP , νQt } decreases,
meaning that we are learning weaker and weaker classifiers, until when we
have converged, the benefit from additional training iterations is negligable.
We plot the density for several iterations of boosting in Figure 6.
2

This is easier in our setting since we have direct access to the density dQ, where
Tolstikhin et al. [2017] estimate it with a cross-validated kernel density estimator.

18

t=0

t=1

t=0

t=1

t=2

t=3

t=2

t=3

(a) Gaussian ring

(b) Randomly placed Gaussians

Figure 6: Visualising the convergence of Qt to P .

6

1.5
1

4

0.5
2
0

1

−0.5

0
0

(a)

2

KL(P, Qt );

4

6

8

C95% (P, Qt );

10

0

NLL.

(b)

2

4

cross entropy;

6

µP ;

8

νQt .

Figure 7: Metrics for analysing convergence over several iterations of boosting.
In (a) we show the coverage metrics at each iteration t. In (b) we plot the
metrics to evaluating the classifier on at batch while training the neural
network, between boosting iterations t.

19

(a) Target

(b) ReLU

(c) Tanh

(d) Softplus

Figure 8: The effect of different activation functions.

5.3

The Effect of the Activation Function

The target distribution P is a mixture of eight isotropic Gaussians arranged
·
in a ring in X = R2 . We modity our simple neural classifier (17) by varying
the activations on the two hidden layers of (17). We compare the resulting
densitites at t = 5 for a selection of activation functions a. Contour plots
are provided in Figure 8 for ReLU, Tanh, and Softplus. We also tried but
have not plotted: ELU with a = 1, this looked very similar to Softplus; Leaky
ReLU, very similar to ordinary ReLU; and Sigmoid, which was disastrous,
converging to a single mode distribution somewhat like a Gaussian.

5.4

Comparison with Tolstikhin et al. [2017]

To compare the performance with AdaGAN we use the exact same network configuration as Tolstikhin et al. [2017, §4.1] for the discriminator and
generator. That is
ReLU

ReLU

GAdG
: L −−−→ R10 −−−→ R5 → X ,
t
DtAdG

dense
ReLU

dense
20 ReLU

ReLU

dense

dense

dense

: X −−−→ R

σ

−−−→ R10 −−−→ R →
− (0, 1),

(18)

where L = R5 . At the beginning of each experimental run, the target
distribution P is a mixture of 10 randomly located isotropic Gaussians with
variance of 1/2. The procedure is as follows: We sample 10k examples from
P , these same examples are then used to run AdaGAN and AdaCovfefe
each for 10 iterations. Since we are training on only 10k examples, compared
to their 64k examples [Tolstikhin et al., 2017, §4.1.1], we run their training
routine for an extra six epochs with early stopping.
20

1

10

0.8
8
0.6
6

0.4
0.2

4

0
2

4

6

8

10

2

(a) NLL (lower is better)

4

6

8

10

(b) Coverage C95% (higher is better).

Figure 9: AdaGAN comparison. Feint lines are individual runs of each
algorith, the solid lines are the median: AdaGAN; AdaBoDE.EST.
1

10

0.8
8
0.6
6

0.4
0.2

4

0
2

4

6

8

10

2

(a) NLL (lower is better).

4

6

8

10

(b) Coverage C95% (higher is better).

Figure 10: AdaGAN comparison using the AdaGAN discriminator architecture (18). Feint lines are individual runs of each algorith, the solid lines are
the median.
Negative Log-Likelihood and C95% are plotted in Figure 9. Early on
AdaBoDE.EST easily outperforms AdaGAN, which gradually only catches
up at iteration 10. However our architecture (17) posesses less than a fifth of
the parameters of AdaGAN. For this reason we reran the experiment using
(18) for the AdaBoDE.EST classifier with a fixed αt = 0.7. The results are
shown in Figure 10 wherein we achieve dramatically better performance both
in NLL and C95% .

21

6

Discussion

Results in the area of iterative approaches to density estimation, including
boosting approaches which are iterative by nature, can be characterized
according to three features: how the convergence is characterized, what kind
of assumptions it does rely upon and finally, whether it is of direct relevance
to current empirical settings for machine learning.
Regarding convergence, there are three kinds of formal results that are
traditionally proven. Some are convergence without rates [Grover and Ermon,
2018, Dudı́k et al., 2004], and others give rates that are negligible with regard
to recent results (including ours) [Rosset and Segal, 2002]. In the third and
final category are explicit convergence rates. Some of the related approaches
have an explicit intractable objective and they rather optimize a tractable
surrogate bound. This is the case for variational inference, where the surrogate
is the evidence lower-bound [Guo et al., 2016, Khan et al., 2016, Locatello
et al., 2017, Miller et al., 2017]. Because of the explicit gap to the intractable
optimum, we do not mean to compare such approaches to ours, but can
summarize most of the formal results in those papers as showing sublinear
convergence, that is, of the form I(P, QT ) ≤ inf Q I(P, Q) + J/T for J > 0
parameter dependant and I defining a suitable divergence.
In the rest of the related approaches, it quite remarkable that all of them
exploit the same Frank–Wolfe-type update (2) [Li and Barron, 2000, Naito
and Eguchi, 2013, Tolstikhin et al., 2017, Zhang, 2003] — even when the
connection to Frank–Wolfe is explicit in few of them [Locatello et al., 2017].
Until recently [Tolstikhin et al., 2017], all these other approaches essentially
displayed sublinear convergence rates [Li and Barron, 2000, Naito and Eguchi,
2013, Zhang, 2003]. This can be compared to our rates from Theorem 19 and
Theorem 22. We compare favorably with them from three standpoints. First,
all these algorithms integrate calls to an oracle/subroutine that needs to solve
a nested optimization problem for its optimum — the contraint put on our
oracle, the weak learner, appears much weaker. Second, all these algorithms
integrate parameters whose computation would require the full knowledge of
distributions [Naito and Eguchi, 2013, Zhang, 2003] or their parameterized
space [Li and Barron, 2000]. It is unclear how approximations would impact
convergence [Miller et al., 2017]. In our case, Theorem 22 just operates on
estimated parameters, straightforward to compute. Third and last, previous
works make more stringent structural assumptions restricting the form of
the optimum [Li and Barron, 2000, Naito and Eguchi, 2013, Zhang, 2003],
22

while we just assume that c?t is bounded, which puts a constraint — easily
enforceable — on the proposals of the weak learner and not on the optimum.
To drill down further in the assumptions required, the very few previous
approaches that manage to beat sublinear convergence to reach geometric convergence — that we reach in Theorem 23 — require very strong assumptions,
such as the constraint that iterates are close enough to the optimum sought
[Tolstikhin et al., 2017, Corollaries 1, 2]. In fact, in this latter work, the
parameterization of the weight α in (2) chosen for their experiments implicitly
imposes the convergence of iterates to this optimum [Tolstikhin et al., 2017,
§4]. In our case, we have shown that equivalent convergence rates can be
obtained without boosting (Corollary 7) but with an assumption which is
used in [Tolstikhin et al., 2017, Corollary 1, Eq. 10], and is thus very strong.
Even when this is not our main result, Corollary 7 is new and interesting
in the light of [Tolstikhin et al., 2017]’s results because (i) it does not make
use of their convex mixture model and (ii) we do not have the additional
technical requirement that P (dQt−1 / dP = 0) < αt , that is, roughly the mass
where dQt−1 = 0 is bounded by the leveraging coefficient. Our main result
on geometric convergence shows that such convergence is within reach with
a much weaker assumptions than [Tolstikhin et al., 2017, Corollary 1, Eq.
10], in fact as weak as the weak learning assumption. To get our result, we
need an additional assumption on the lower-boundedness of the log-errors
εt a. e. via the WDA, but this is still very weak considering that we fit
an exponential family and in interesting applications like image processing,
domain X is closed so unless dP is allowed to peak arbitrarily, we essentially
get WDA for reasonable Γε .
Now, why is the assessment of all assumptions important in the light of
experimental settings? Because it brings them to a trial by fire, as to whether
results survive to experimental machine learning, with available information
which is in general a partial estimated snapshot of the theory. It should be
clear at this point that, with the sole exception of a subset of variational
approaches — which, again, settle for an explicitly tractable surrogate of
the objective —, all previous approaches would fail at this test, [Grover and
Ermon, 2018, Guo et al., 2016, Li and Barron, 2000, Locatello et al., 2017,
Naito and Eguchi, 2013, Tolstikhin et al., 2017, Zhang, 2003]. They would
all fail essentially because in practice, we obviously would not have access
to P to test assumptions nor carry out fine-grained optimisation involving
P . To our knowledge, our result in §4.4 is the first attempt to provide an
algorithm fully executable on current experimental learning settings and
23

whose convergence relies on assumptions that would also easily be testable or
enforceable empirically.
We must insist however on the fact that all previous approaches that
investigate variational inference or GANs get a black box sampler which
may be hard to train but it always easy to sample from, in particular high
dimensions [Guo et al., 2016, Khan et al., 2016, Locatello et al., 2017, Miller
et al., 2017, Tolstikhin et al., 2017] — this is clearly where the bottleneck of
our theory lies currently, even when our experiments display that efficient
sampling is available up to moderate dimensions. We conjecture that it is
much further scalable.

7

Conclusion

The idea of learning a density in an iterative, “boosting”-type combination
of proposal densities has recently met with significant attention. Typically,
aproaches use a subroutine oracle, e.g. to fit the coefficients in the combination
of densities. In all cases displaying significant convergence rates, such an
oracle would be required to satisfy very strong constraints.
In this paper, we have shown that all it takes to learn a density iteratively
in a boosting fashion is a weak learner in the original sense of the Probably
Approximately Correct learning model, leading to comparable or better
convergence bounds than previous approaches at comparatively very reduced
price in assumptions. We derive this result through a series of related
contributions, including (i) a finer characterization of the solution to the
f -GAN problem and (ii) a full characterization of the distribution we learn
in exponential families.
Experimentally, our approach shows very promising results for an early
capture of modes, and significantly outperforms AdaGAN during the early
boosting iterations using a comparatively very small architecture. Our experiments leave however open the challenge to obtain a black box sampler
for domains with moderate to large dimension. We conjecture that the full
characterization that we get of the distribution learned might be of significant
help to tackle this challenge.

24

References
Syed Mumtaz Ali and Samuel D Silvey. A general class of coefficients of
divergence of one distribution from another. Journal of the Royal Statistical
Society. Series B (Methodological), pages 131–142, 1966.
S.-I. Amari and H. Nagaoka. Methods of Information Geometry. Oxford
University Press, 2000.
A. Banerjee, S. Merugu, I. Dhillon, and J. Ghosh. Clustering with Bregman
divergences. JMLR, 6:1705–1749, 2005.
O. Barndorff-Nielsen. Information and Exponential Families in Statistical
Theory. Wiley Publishers, 1978.
Imre Csiszár. Information–type measures of difference of probability distributions. Studia Scientiarum Mathematicarum Hungarica, 17:123–149,
1967.
M. Dudı́k, S.-J. Phillips, and R.-E. Schapire. Performance guarantees for
regularized maximum entropy density estimation. In COLT, 2004.
Y. Freund and R. E. Schapire. A Decision-Theoretic generalization of on-line
learning and an application to Boosting. JCSS, 55:119–139, 1997.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David WardeFarley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative
adversarial nets. In Advances in neural information processing systems,
pages 2672–2680, 2014.
Aditya Grover and Stefano Ermon. Boosted generative models. In AAAI,
2018.
Jacques Guélat and Patrice Marcotte. Some comments on Wolfe’s ’away step’.
Math. Program., 35:110–119, 1986.
F. Guo, X. Wang, K. Fan, T. Broderick, and D.-B. Dunson. Boosting
variational inference. CoRR, abs/1611.05559, 2016.
Michael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript,
45:105, 1988.
25

M.-E. Khan, R. Babanezhad, W. Lin, M.-W. Schmidt, and M. Sugiyama.
Faster stochastic variational inference using proximal-gradient methods
with general divergence functions. In UAI, 2016.
Jonathan Q Li and Andrew R Barron. Mixture density estimation. In
Advances in neural information processing systems, pages 279–285, 2000.
F. Locatello, R. Khanna, J. Ghosh, and G. Rätsch. Boosting variational
inference: an optimization perspective. CoRR, abs/1708.01733, 2017.
C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. RamirezAlfonsin, and B. Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics, pages 1–54. Springer Verlag, 1998.
A.-C. Miller, N.-J. Foti, and R.-P. Adams. Variational boosting: Iteratively
refining posterior approximations. In ICML, pages 2420–2429, 2017.
K. Naito and S. Eguchi. Density estimation with minimization of U-divergence.
Machine Learning, 90(1):29–57, 2013.
XuanLong Nguyen, Martin J Wainwright, and Michael I Jordan. Estimating
divergence functionals and the likelihood ratio by convex risk minimization.
IEEE Transactions on Information Theory, 56(11):5847–5861, 2010.
Richard Nock and Frank Nielsen. A Real Generalization of discrete AdaBoost.
Artificial Intelligence, 171:25–41, 2007.
Richard Nock and Frank Nielsen. On the efficient minimization of classificationcalibrated surrogates. In Advances in neural information processing systems,
pages 1201–1208, 2008.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f -gan: Training
generative neural samplers using variational divergence minimization. In
Advances in Neural Information Processing Systems, pages 271–279, 2016.
Jean-Paul Penot. Calculus without derivatives, volume 266. Springer Science
& Business Media, 2012.
M.-D. Reid and R.-C. Williamson. Composite binary losses. JMLR, 11:
2387–2422, 2010.

26

Mark D Reid and Robert C Williamson. Information, divergence and risk
for binary experiments. Journal of Machine Learning Research, 12(Mar):
731–817, 2011.
S. Rosset and E. Segal. Boosting density estimation. In NIPS, pages 641–648,
2002.
R. E. Schapire. The strength of weak learnability. Machine Learning, pages
197–227, 1990.
R. E. Schapire and Y. Singer. Improved boosting algorithms using confidencerated predictions. Machine Learning, 37:297–336, 1999.
S. Simić. On a new converse of Jensen’s inequality. Publications de l’Institut
Mathématique, 85:107–110, 2009a.
S. Simić. On an upperbound for Jensen’s inequality. Journal of Inequalities
in Pure and Applied Mathematics, 10, 2009b.
I.-O. Tolstikhin, S. Gelly, O. Bousquet, C.-J. Simon-Gabriel, and B. Schölkopf.
Adagan: Boosting generative models. In NIPS, pages 5430–5439, 2017.
L. G. Valiant. A theory of the learnable. C. ACM, 27:1134–1142, 1984.
T. Zhang. Sequential greedy approximation for certain convex optimization
problems. IEEE Trans. IT, 49:682–691, 2003.

A

Proofs of Theoretical Results

Lemma 4. Assume f : R+ → R+ is strictly convex and twice differentiable,
and F is a normed space of functions X → int(dom f ). Let F ⊆ F and
ū ∈ arg minu∈F J(u). If J is finite on a neighbourhood of ū, then ū ∈
dP/dQ − NF (ū). If, in addition, F is convex with dP/dQ ∈ int F, then
ū = dP/dQ.
Proof. Because f is twice differentiable on int(dom f ), and J is finite on a
neighbourhood of ū, J is Fréchet differentiable at ū with
J 0 (ū) = ((f ∗ )0 ◦ f 0 ◦ ū) · (f 00 ◦ ū) · dQ − (f 0 ◦ ū) · dP.
= ū · (f 00 ◦ ū) · dQ − (f 00 ◦ ū) · dP,
27

where (f ∗ )0 = (f 0 )−1 since f is strictly convex. By hypothesis J attains its
minimum on F at ū, thus Fermat’s rule [Penot, 2012, Theorem 2.97, p. 170]
yields
0 ∈ J 0 (ū) + NF (ū) ⇐⇒ 0 ∈ ū · (f 00 ◦ ū) · dQ − (f 00 ◦ ū) · dP + NF (ū)
dP
1
+ 00
· NF (ū)
⇐⇒ 0 ∈ ū −
dQ (f ◦ ū) · dQ
dP
⇐⇒ ū ∈
− NF (ū),
dQ
where the final biconditional follows since NF (ū) is a cone.
Now, suppose dP/dQ ∈ int F with F convex. Then the Fréchet cone
becomes usual normal cone [Penot, 2012, Ex. 6, p. 174],
·

NF (ū) = {u∗ ∈ F∗ : (∀v ∈ F)

hu∗ , v − ūi ≤ 0}.

It’s immediate from the definition that NF always contains 0. We use a
contradiction to show that NF (ū) ⊆ {0}. Take z ∗ =
6 0 ∈ NF (ū). Let
·
¯ implies 0 ∈ int Fū . Thus there is a
Fū = F − ū. First note that intu
closed symmetric neighbourhood U with 0 ∈ U ⊆ int Fū . The Hahn–Banach
strong separation theorem [Penot, 2012, Theorem 1.79, p. 55] guarantees the
existence of a vector u ∈ U such that
hz ∗ , ui > 0 ⇐⇒ (∃v ∈ F)

hz ∗ , v − ūi > 0,

contradicting the hypothesis that z ∗ ∈ NF . Thus NF (dP/dQ) = {0}.



Lemma 5. For any αt ∈ [0, 1] and εt ∈ [0, +∞)X , letting dQt as in (4) and
dt as in (6), we have:


Zt
≤ (EP εt )αt .
exp αt EQt−1 log εt − rKL(P, Qt−1 ) ≤
Zt−1
Proof. Since αt ∈ [0, 1], by Jensen’s inequality it follows that
Z
 αt
 αt
dP
αt
EQt−1 dt ≤ EQt−1 dt
=
· εt dQt−1
= (EP εt )αt . (19)
dQt−1
The upper bound on Zt /Zt−1 follows:
(19)
Zt (24)
= EQt−1 dαt t ≤ (EP εt )αt .
Zt−1

28

For the lower bound on Zt /Zt−1 , note that


Zt
(24)
= log EQt−1 dαt
log
Zt−1
≥ αt EQt−1 log dt



dP
= αt EQt−1 log εt + log
,
dQt−1
which implies the lemma.



The error term allows us to bound the KL divergence of P from Qt as
follows.
Theorem 6. For any αt ∈ [0, 1] and εt ∈ [0, +∞)X , letting dQt as in (4)
and dt as in (6), we have:
KL(P, Qt |αt ) ≤ (1 − αt ) KL(P, Qt−1 ) + αt (log EP εt − EP log εt ).

(8)

Proof. First note that
dQt =

1
1
Zt−1 αt
dQ̃t = dαt t dQ̃t−1 =
d dQt−1 .
Zt
Zt
Zt t

(20)

Now consider the following two identities:



Zt−1
−αt log EP εt ≤ log
,
Zt
which follows from Lemma 5, and


Z  
dP
− αt log dt dP
log
dQt−1




Z  
dP
dP
=
log
− αt log
− αt log εt dP
dQt−1
dQt−1


Z
Z
dP
= (1 − αt ) log
dP − αt log εt dP
dQt−1
= (1 − αt ) KL(P, Qt−1 ) − αt EP log εt .

29

(21)

(22)

Then

dP
dP
KL(P, Qt ) = log
dQt



Z  
dP
Zt−1 αt
(20)
=
log
dP
− log
d
dQt−1
Zt t




Z  
dP
Zt−1
log
=
− αt log dt dP − log
dQt−1
Zt
|
{z
} |
{z
}
Z



(22)

(21)

≤ (1 − αt ) KL(P, Qt−1 ) + αt (log EP εt − EP log εt ),
as claimed.



Corollary 7. For any αt ∈ [0, 1] and εt ∈ [0, +∞)X , letting dQt as in (4),
dt as in (6) and dRt from (10) and (11), if Rt satisfies
KL(P, Rt ) ≤ γ KL(P, Qt−1 )
for γ ∈ [0, 1], then
KL(P, Qt |αt ) ≤ (1 − αt (1 − γ)) KL(P, Qt−1 ).
Proof. We first show
KL(P, Qt |αt ) ≤ (1 − αt ) KL(P, Qt−1 ) + αt KL(P, Rt ).

(23)

By definition εt = dRt /dP . The rightmost term in (8) reduces as follows
!
Z
Z
dR̃t
dR̃t
log EP εt − EP log εt = log
dP − log
dP
dP
dP


Z
Z
dP
= log dR̃t + log
dP
dR̃t


Z
Z  
dP
+ log dR̃t dP
=
log
dR̃t


Z
Z
dP
= log
· dR̃t dP
dR̃t


Z
dP 
= log 1
dP,
R
dR̃t
dR̃
t

which completes the proof of (23). The proof of (13) is then immediate. 
30

A.1

Results From §4

Proposition 8. The normalisation factors can be written recursively with
Zt = Zt−1 · EQt−1 dαt t .
Proof. We just need to write
Z
Z
Z
Zt
1
1
αt
=
dQ̃t =
dt dQ̃t−1 = dαt t dQt−1 = EQt−1 dαt t (24)
Zt−1
Zt−1
Zt−1
thus Zt = Zt−1 · EQt−1 dαt t .



Proposition 9. The distribution Qt is an exponential family distribution
·
·
with natural parameter α = (α1 , . . . , αt ) and sufficient statistic c(x) =
(c1 (x), . . . , ct (x)).
Proof. We can convert the binary classifiers c1 , . . . , ct ∈ C(X ) to a sequence
of density ratios (di ) using the connections in §3, which yields
·

dαi i = (ϕ ◦ σ ◦ ci )αi = exp ◦ (αi ci ).
In this setting, the multiplicative density at round t is
t
Y
1
dαi i dQi (x)
αi
i=1 di dQ0 i=1
!
t
X
= exp
αi ci (x) − C(α) dQ0 (x),

(4)

dQt (x) = R Qt

i=1

R
P
·
with α = (α1 , . . . , αt ) and C(α) = log exp( ti=1 αi ci ) dQ0 , which is an
exponential family distribution with natural parameter α, sufficient statistic
·
c(x) = (c1 (x), . . . , ct (x)), cumulant function C(α), reference measure Q0 .
We note that in the general case, it may be the P
case that for some nonall-zero constants z0 , z1 , . . . , zt ∈ R, we have z0 = ti=1 zi ci (x), that is, the
representation is not minimal.

Lemma 10. Suppose γP = γQ = γ in WLA and WLA∗ , without loss of
generality. Then there exists WeakLearn satisfying WLA iff there exists
WeakLearn∗ satisfying WLA∗ .

31

Proof. To simplify notations, we suppose without loss of generality that
C(X ) ⊆ [−1, 1]X .
(⇒) Let D be a distribution on X × {−1, +1}. It can be factored as
a triple (π, P, N ) where P is a distribution over the positive examples, N
is a distribution over negative examples and π is the mixing probability,
·
π = PrD [y = +1]. Now, feed P and N in lieu of P and Qt , repectively.
We get ct which, from WLA, satisfies EN [−ct ] ≥ γ and EP [ct ] ≥ γ, which
implies
ED [yct ] = π EP [ct ] + (1 − π) EN [−ct ] ≥ πγ + (1 − π)γ = γ
and we get our weak learner WeakLearn∗ satisfying WLA∗ .
(⇐) We create a two-class classification problem in which observations
from P have positive class y = +1, observations from Qt have negative class
y = −1 and there is a special observation x∗ ∈ X which is equally present
with probability 1 − 2π in both the positive and negative class. Hence, we
are artificially increasing the difficulty of the problem by making its Bayes
optimum worse. Obviously, WLA∗ having to hold under any distribution,
it will have to hold under the distribution D that we create. To explicit D,
consider π ∈ [0, 1/2] and the following sampler for D:
• sample z ∈ [0, 1] uniformly;
– if z ≤ (1 − 2π)/2 return (x∗ , +1);
– else if z ≤ 1 − 2π return (x∗ , −1);
– else if z ≤ 1 − π, return (x ∼ P, +1);
– else return (x ∼ Qt , −1);
Let D denote the distribution induced on X × {−1, +1}. Remark that the
error of Bayes optimum is at least 1/2 − π. Let ct returned by WeakLearn∗ .
We have because of WLA∗ ,


1 − 2π 1 − 2π
ct (x∗ ) = π(µP + νQt−1 ) ≥ γ
ED [yct ] = π(µP + νQt−1 ) +
−
2
2
Consider
π=

γ
1+γ
32

Which makes
µP + νQt−1 ≥ 1 + γ.
It easily comes that if µP < γ, then we must have νQt−1 > 1, which is not
possible, and similarly if νQt−1 < γ, then we must have µP > 1, which is also
impossible. Therefore we have both µP ≥ γ and νQt−1 ≥ γ, and we get our
weak learner WeakLearn meeting WLA, as claimed.

A.1.1

Proof of Theorem 19

The proof of Theorem 19 is achieved in two steps: (i) any ct meeting WLA
can be transformed through scaling into a classifier that we call Properly
Scaled without changing it satisfying WLA (for the same parameters γP , γQ ),
(ii) Theorem 19 holds for such Properly Scaled classifiers.
Definition 11. The classifier ct is said to be Properly Scaled (PS) if it meets:
exp(2c?t ) ≤ 2 + µP c?t


µP c?t
EQt−1 exp(ct ) ≤ exp
.
4

(PS.1)
(PS.2)

Hence, we first show how any classifier meeting WLA can be made PS
without changing µP nor νQt−1 (hence, still meeting WLA), modulo a simple
positive scaling. The proof involves a reverse of Jensen’s inequality which
is much simpler than previous bounds [Simić, 2009a,b] and of independent
interest.
Our proof will equivalently give upper bounds on c?t that make ct PS. We
note that our proof is constructive, that is, we give eligible upper bounds for
c?t . The proof of Theorem 16 is split in several lemmata, the first of which is
straightforward since µP ≥ 0 under WLA.
Lemma 12. Suppose ct meets WLA. Then, (PS.1) holds for any c?t ≤
log(2)/2.
To prove how to satisfy (PS.2), we use the notions of Bregman divergences
and Bregman information. For ϕ : R → R convex differentiable with derivative
ϕ0 , we define the Bregman divergence with generator ϕ as Dϕ (zkz 0 ) = ϕ(z) −
ϕ(z 0 ) − (z − z 0 )ϕ0 (z 0 ). Following [Banerjee et al., 2005], we define the minimal
33

Bregman information of (ct , Qt−1 ) (or just Bregman information for short)
relative to ϕ as
·

Iϕ (ct ; Qt−1 ) = EQt−1 [Dϕ (ct k EQt−1 ct )].
The Bregman information is a generalization of the variance for which ϕ(z) =
z 2 . Jensen’s inequality would give us a lowerbound, but we need an upperbound.
We devise for this objective a reverse of Jensen’s inequality. We suppose that
ct takes values in [a, b], where we would thus have |a| or b which would be c?t .
Lemma 13. (Reverse of Jensen’s inequality) Suppose ϕ strictly convex differentiable and ct (x) ∈ [a, b] for all x ∈ X . Then,

 0

0
? 0 ϕ (a) − ϕ (b)
Iϕ (ct ; Qt−1 ) ≤ Dϕ u (ϕ )
,
(26)
a−b
where u can be chosen to be a or b.
Proof. The proof is in fact straightforward, as illustrated in Figure 11.



We now show how to satisfy (PS.2).
Lemma 14. Suppose ct meets WLA and


1 − exp(−2γQ )
γP
?
+
.
ct ≤
4
2
Then


µP c?t
EQt−1 exp(ct ) ≤ exp
,
4
that is, (PS.2) holds.
Proof. Consider ϕ(z) = exp(z) and so ϕ? (z) = z log z − z in Lemma 13.
Suppose without loss of generality that a = −c?t , b = c?t . We get
Iexp (ct ; Qt−1 ) = EQt−1 exp(ct ) − exp EQt−1 ct

 0 ?

0
?
?
? 0 ϕ (ct ) − ϕ (−ct )
≤ Dϕ ct (ϕ )
.
2c?t

34

Figure 11: Proof of Lemma 13. The tangent represented is parallel to the
chord linking (a, ϕ(a)) and (b, ϕ(b)). The LHS of (26) can be represented by
the vertical difference between the blue point (always in the grey area) and
the green point (always on ϕ). The RHS of (26), as a Bregman divergence, is
the difference between the curve and the tangent measured in either a or b.
Now, we just need to ensure that

 0 ?



0
?
µP c?t
?
? 0 ϕ (ct ) − ϕ (−ct )
Dϕ ct (ϕ )
≤ exp
− exp(−νQt−1 c?t ),(27)
?
2ct
4
as indeed we shall then have, because of WLA,


γP c?t
− exp(−γQ c?t ) + exp EQt−1 ct
EQt−1 exp(ct ) ≤ exp
4


µP c?t
− exp(−νQt−1 c?t ) + exp(−νQt−1 c?t )
≤ exp
4


µP c?t
= exp
,
4
which is the statement of the lemma.
35

·

Proposition 15. Pick ϕ = exp. If |z| ≤ 2, then
 0


0
? 0 ϕ (z) − ϕ (−z)
Dϕ z (ϕ )
≤ z2.
2z
Proof. Equivalently, we need to show




1
1
1
1
2
−
+ exp(−z)
+
z ≥ exp(z)
2 2z
2 2z

 

exp(z) − exp(−z)
exp(z) − exp(−z)
+
log
.
2z
2z
We split the proof in two. First, let us fix


1
1
1
1
· 2 exp(z) 2 − 2z + exp(−z) 2 + 2z
g1 (z) =
.
z2
We remark that
exp(−z)(−z 2 − 3z − 3 + exp(2z)(z 2 − 3z + 3))
.
g10 (z) =
2z 4
·

We then remark that, letting g2 (z) = −z 2 − 3z − 3 + exp(2z)(z 2 − 3z + 3),
X 2k z k+2 X 3 · 2k z k+1 X 3 · 2k z k
g2 (z) = −z 2 − 3z − 3 +
−
+
k!
k!
k!
k≥0
k≥0
k≥0
X 2k−2 z k
X 3 · 2k−1 z k X 3 · 2k z k
−
+
(k
−
2)!
(k
−
1)!
k!
k≥2
k≥1
k≥0

X 2k−2
3 · 2k−1
3 · 2k k
=
−
+
z
(k − 2)! (k − 1)!
k!
k≥2

X 2k−2
3 · 2k−1
3 · 2k k
=
−
+
z
(k
−
2)!
(k
−
1)!
k!
k≥5
= −z 2 − 3z − 3 +

=

X
k≥5

k 2 − 7k + 12

 2k−2 z k
.
k!

We then check that z 7→ z 2 − 7z + 12 < 0 only for z ∈ (3, 4). That is, it
is never negative over naturals so g2 (z) ≥ 0, ∀z ≥ 0. We also check that
lim0 g10 (z) = 0 and so g1 (z) is increasing for z ≥ 0. Finally,


1
exp(2)
3
7.81
g1 (2) = ·
+
<
< 1,
2
4
4 exp(2)
8
36

which shows that
(∀|z| ≤ 2)





1
1
1
z2
1
−
+ exp(−z)
+
≤ ,.
exp(z)
2 2z
2 2z
2

(28)

(the analysis for z < 0 uses the fact that the function is even) We now show
that we have
z2
exp(z) − exp(−z)
≤ 1 + , ∀z ∈ [−2, 2].
2z
4

(29)

Hence, we want to show that exp(z) ≤ exp(−z) + 2z + z 3 /2 for z ∈ [−2, 2].
We now have exp(−z) ≥ 1 − z + z 2 /2 − z 3 /6 + z 4 /24 − z 5 /120 for z ≥ 0, so we
just need to show exp(z) ≤ 1 − z + z 2 /2 − z 3 /6 + z 4 /24 − z 5 /120 + 2z + z 3 /2 =
1 + z + z 2 /2 + z 3 /3 + z 4 /24 − z 5 /120 + 2z + z 3 /2 for z ∈ [0, 2] (we will then
use the fact that both functions in (29) are even), which simplifies, using
Taylor series for exp, in showing
X zk
z3
z5
≤
− , ∀z ∈ [0, 2],
k!
6
60
k≥6
or after dividing both sides by z 3 > 0 (the inequality is obviously true for
z = 0),
X
k≥6

1
z k−3
1 z2
·
≤ − , ∀z ∈ (0, 2],
k(k − 1)(k − 2) (k − 3)!
6 60

P
z k−3
≤
Since k(k − 1)(k − 2) ≥ 120 for k ≥ 6, it is enough to show that k≥6 (k−3)!
P
P
k−3
k
z
20 − 2z 2 . But k≥6 (k−3)!
= k≥3 zk! = exp(z) − 1 − z − z 2 /2, so we just
need to show that exp(z) ≤ 21 + z − 3z 2 /2 for z ∈ (0, 2], which is easy to
show as the rhs is concave, decreasing for z ≥ 1/3 and intersecting exp for
z ≥ 5/2. So (29) holds. Since log(z) ≤ z − 1, we get

 

exp(z) − exp(−z)
exp(z) − exp(−z)
z exp(z) − z exp(−z)
log
≤
2z
2z
8
Now, we have exp(z) − exp(−z) − 4z ≤ 0 for z ∈ [0, 2], since the function is
strictly convex for z ≥ 0 with two roots at z = 0 and z > 2. Reorganising,
this shows that (z exp(z) − z exp(−z))/8 ≤ z 2 /2 for z ∈ [0, 2], and so
 


exp(z) − exp(−z)
z2
exp(z) − exp(−z)
log
≤ , ∀z ∈ [0, 2].
2z
2z
2
37

Putting it together with (28), we now have
 0


0
? 0 ϕ (z) − ϕ (−z)
Dϕ z (ϕ )
2z




1
1
1
1
−
+ exp(−z)
+
= exp(z)
2 2z
2 2z

 

exp(z) − exp(−z)
exp(z) − exp(−z)
+
log
2z
2z
2
2
z
z
+
=
2
2
2
=z
for z ∈ [0, 2], and therefore, since both functions are even, the same holds for
z ∈ [−2, 0] and completes the proof.

To show (27), we therefore just need to ensure c?t small enough so that


µP c?t
?2
ct ≤ exp
− exp(−νQt−1 c?t ).
(30)
4
Because exp(−νQt−1 c?t ) is convex, it is upper-bounded over the interval [0, 2]
by its chord between its two points in abscissae 0 and 2,
1 − exp(−2νQt−1 ) ? ?
ct , ∀ct ∈ [0, 2],
2
and we also have, since exp(z) ≥ 1 + z,


µP c?t
µP c?t
≥1+
.
exp
4
4
exp(−νQt−1 c?t ) ≤ 1 −

To ensure (30), it is therefore sufficient, as long as c?t ∈ (0, 2], that


1 − exp(−2νQt−1 ) ?
µP
?2
ct ≤
+
ct ,
4
2
which, after simplification and considering WLA, is achieved provided


γP
1 − exp(−2γQ )
?
ct ≤
+
.
(31)
4
2
There remains to check that the condition of Proposition 15 applies, that
is, c?t ≤ 2. The maximal value of the rhs in (31), taking into account that
γP , γQ ≤ 1, is 1/4 + (1 − exp(−2))/2 ≈ 0.57 < 2, which shows that the
condition of Proposition 15 indeed applies and proves Lemma 14.

38

Theorem 16. Suppose ct satisfies WLA. Then there exists a constant η > 0
such that η · ct satisfies WLA and is PS.
Proof. Even when better bounds are possible, the combination of Lemma 12
and Lemma 14 show that any ct satisfying the WLA, positively scaled so that
c?t ≤ log(2)/2, still satisfies WLA and is PS, as claimed.

We shall now prove Theorem 19. The proof mainly consists of two
lemmata, one showing that EQt−1 exp(αt ct ) is small, the second one showing,
under conditions on ct , that EQt−1 exp(ct ) is conveniently upper-bounded by
EQt−1 exp(αt ct ), leading to the theorem.
 1+ν

· 1
Qt−1
. Then
Lemma 17. Let αt = 2c? log 1−νQ
t
t−1
q
EQt−1 exp(αt ct ) ≤ 1 − νQ2 t−1 .
Proof. We know [Nock and Nielsen, 2007] that
(∀a, b ∈ [−1, 1]) 1 − ab ≥
·

√

1−

a2




b
1+a
exp − log
.
2
1−a

(32)

·

Let a = νQt−1 and b = −ct /c?t , for short. Then we obtain

 

1 + νQt−1
1
exp(αt ct ) = exp − −ct · ? log
2ct
1 − νQt−1
ct
1
+
ν
(32)
Qt−1 c?
t
≤ q
2
1 − νQt−1


1 − νQt−1 · − cc?t
t
q
=
,
1 − νQ2 t−1
which implies the lemma.

(33)


Lemma 18. Fix any J ≥ 0. Suppose that the two conditions hold:
 
J
EQt−1 exp(ct ) ≤ exp
,
2

νQt−1 ≤
39

J
.
1+J

(34)

(35)

Then,
EQt−1 exp(ct ) ≤ q

1
1 − νQ2 t−1

· EQt−1 exp(αt ct + J).

Proof. Jensen’s inequality yields


EQt−1 exp(αt ct ) ≥ exp EQt−1 αt ct = exp −αt c?t νQt−1 ,
hence we rather show the stronger statement
EQt−1 exp(ct ) ≤ q

1
1 − νQ2 t−1


· exp −αt c?t νQt−1 + J .

We use two inequalities:
(∀z ∈ [0, 1])



1+z
1
2z 2
≥ z log
≥ 4 log √
.
1−z
1−z
1 − z2

(36)

Let us summarize these as A ≥ B ≥ C. To first check these inequalities, we
remark:
·

• to check A ≥ B, we simplify it: it yields equivalently g1 (z) = z 2 (1+z) ≥
·
−(1 − z 2 ) log(1 − z 2 ) = g2 (z). We then check that g20 (z) = 2z(1 + log(1 −
z 2 )) while g10 (z) = 2z(1 + 3z/2). Both derivatives are continuous with
the same limit in 0 and it is easy to check that for z ≥ 0, g20 (z) ≤ g10 (z).
Since g1 (0) = g2 (0), we get A ≥ B;
·

• to check B ≥ C, we simplify it, which yields equivalently g3 (z) =
(z −2) log(1−z)−(z +2) log(1+z) ≥ 0. We have g300 (z) = 4z 2 /(z 2 −1)2 ≥
0, which shows the strict convexity of the function. We also have
g30 (0) = g3 (0) = 0, which gives g3 (z) ≥ 0, ∀z and shows B ≥ C.
With the latter ineq. (36) and the expression of αt for the regular boosting

40

regime, we get

1
q
· exp −αt c?t νQt−1 + J
1 − νQ2 t−1

!
!
νQ
1 + νQt−1 
1
(37)
= expJ + log q
− t−1 log
2
1 − νQt−1
1 − νQ2 t−1



νQt−1
1 + νQt−1
≥ exp J −
log
4
1 − νQt−1
!
2νQ2 t−1
1
≥ exp J − ·
.
(38)
4 1 − νQt−1
The last inequality follows from the former ineq. (36). Suppose now that we
can ensure
2νQ2 t−1
≤ 2J.
1 − νQt−1

(39)

It would follow from (38) that
1

q
· exp
1 − νQ2 t−1

−αt c?t νQt−1



1
+ J ≥ exp J − · 2J
4
 
J
= exp
,
2


and so to prove the lemma, we would just need
 
J
EQt−1 exp(ct ) ≤ exp
,
2
which is precisely (34). To get (39), we equivalently need νQ2 t−1 +JνQt−1 −J ≤ 0,
that is,
νQt−1 ≤

√
1
· (−J + J 2 + 4J)
2

(40)

√
·
To prove a simpler equivalent condition, we let g4 (z) = (1 + z) z 2 + 4z/(z(3 +
z)). We easily get lim↓0 g4 (z) = +∞, lim+∞ g4 (z) = 1 and g40 (z) = −6(z +
41

·

4)/N with N = (z 2 + 4z)3/2 (3 + z)2 ≥ 0, so g4 (z) ≥ 1, ∀z ≥ 0 and
√ reordering
this inequality yields equivalently z/(1 + z) ≤ (1/2) · (−z + z 2 + 4z) for
z ≥ 0, so to get (40), we just require νQt−1 ≤ J/(1 + J), which is (35), and
ends the proof of Lemma 18.

We are now in a position to prove Theorem 19.
Theorem 19. In the regular boosting regime and under WLA,


1 + νQt−1
µP
KL(P, Qt |αt ) ≤ KL(P, Qt−1 ) −
log
.
4
1 − νQt−1
Proof. We have

EP εt = EQt−1


dP
· εt = EQt−1 exp(ct ).
dQt−1

(41)

Hence, combining successively the statements of Lemma 18 (we check below
that the conditions of the lemma are indeed satisfied) and Lemma 17, we get:
log EP εt = log EQt−1 exp(ct )


1
≤ log q
· EQt−1 exp(αt ct + J)
1 − νQ2 t−1


EQt−1 exp(αt ct )
· exp(J)
= log q
2
1 − νQt−1
≤ log exp(J)
= J.

(42)

(43)

On the other hand, WLA yields


dP
?
· εt = KL(P, Qt−1 ) + EP log εt .
µP ct = EP ct = EP log
dQt−1

(44)

Since αt ≥ 0, it follows from Theorem 6 and (44), (43) in this order that
KL(P, Qt ) ≤ KL(P, Qt−1 ) − αt (KL(P, Qt−1 ) + EP log εt ) + αt log EP ε(45)
t
?
= KL(P, Qt−1 ) − αt µP ct + αt log EP εt
≤ KL(P, Qt−1 ) − αt µP c?t + αt J
= KL(P, Qt−1 ) − αt (µP c?t − J).
(46)
42

·

It remains to fix J = µP c?t /2, and we get
αt µP c?t
2 

1 + νQt−1
µP
= KL(P, Qt−1 ) −
log
,
4
1 − νQt−1

KL(P, Qt ) ≤ KL(P, Qt−1 ) −

(47)

which is the statement of the theorem. We end up the proof of Theorem 19 by
showing that the PS property for ct implies that the conditions of Lemma 18
are satisfied — hence, Theorem 19 is shown for ct being PS, which we recall
is always possible from Theorem 16 when ct satisfies the WLA. While it is
clear that (34) is one of the PS properties for ct , we still need to show that
the PS ensures (35) with J = µP c?t /2, that is, we need to show that
νQt−1 ≤

µP c?t
.
2 + µP c?t

(48)

Recall that we are in the regular boosting regime where we do not clamp αt ,
and therefore, if we let
·

νc?t =

exp(2c?t ) − 1
∈ (0, 1),
exp(2c?t ) + 1

(49)

then we know that νQt−1 ≤ νc?t , so to have (48), it suffices to ensure νc?t ≤
µP c?t /(2 + µP c?t ), which equivalently yields
exp(2c?t ) ≤ 2 + µP c?t ,
which is the first PS property. This ends the proof of Theorem 19.
A.1.2

Proof of Theorem 21

We follow some of the same steps as for Theorem 19.
·

Lemma 20. Let αt = 1. Then
1 − νQ νc ?
EQt−1 exp(ct ) ≤ q t−1 t ,
1 − νc2?t
where νc?t is defined in (49).
43



Proof. We have this time EQt−1 exp(ct ) = EQt−1 exp(αt ct ). We use again (32)
with a = νc?t and get, instead of (33):


1 − νc?t · − cc?t
t
q
,
exp(αt ct ) ≤
2
1 − νc?t
which implies the lemma after taking the expectation and remarking that for
the choice a = νc?t , αt = 1.

Theorem 21. In the high boosting regime,
KL(P, Qt |αt ) ≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·

!
1
δt−1
+
.
2 1 − νc2?t

Proof. Since we get a direct bound on EQt−1 exp(ct ), we can achieve the proof

44

of Theorem 21 via (41) and (45) as
KL(P, Qt ) ≤ KL(P, Qt−1 ) − αt (KL(P, Qt−1 ) + EP log εt ) + αt log EP εt
≤ KL(P, Qt−1 ) − µP c?t + log EP εt
1 − νQ νc?
≤ KL(P, Qt−1 ) − µP c?t + log q t−1 t
1 − νc2?t
= KL(P, Qt−1 ) − µP c?t


1 − νc2?t
?
νc

+ log q
− (νQt−1 − νc?t ) · q t
2
2
1 − νc?t
1 − νc?t
= KL(P, Qt−1 ) − µP c?t


q
?
ν
c

+ log 1 − νc2?t − (νQt−1 − νc?t ) · q t
2
1 − νc?t
1
· log(1 − νc2?t )
2
!
νc?t
+ log 1 − (νQt−1 − νc?t ) ·
1 − νc2?t

= KL(P, Qt−1 ) − µP c?t +

≤ KL(P, Qt−1 ) −

µP c?t

−

νc2?t
2

− (νQt−1 − νc?t ) ·

≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·

νc?t
1 − νc2?t

(50)

!
δt−1
1
+
,
2 1 − νc2?t

where we have let νQt−1 = (1 + δt−1 )νc?t . In (50), we have used log(1 − x) ≤
−x.

Theorem 22. Suppose WLA holds at each iteration. Then using Qt as in
(4) and αt as in (14), we are guaranteed that KL(P, QT ) ≤ % after a number
of iterations T satisfying:
T ≥2·

KL(P, Q0 ) − %
.
γP γQ

Proof. The proof stems from the regular boosting regime, using log((1 +
z)/(1 − z)) ≥ 2z for z ≥ 0. Better rates are possible using the high boosting
45

regime, and in any case, Qt as in (4) and αt as in (14) define a simple boosting
algorithm to come up with an analytical expression for QT that provably
converges to P .

We reformulate the theorem involving a new notation for readability
purpose in the proof.
·

Theorem 23. Suppose WLA holds with γQ = γr · c?t for some γr > 0 and
WDA hold at each boosting iteration. Then we get after T boosting iterations:

T
min{2, γr }γP
KL(P, QT ) ≤ 1 −
· KL(P, Q0 ).
2(1 + Γε )
Proof. We proceed in two steps, first showing how WDA bounds KL(P, Qt−1 ).
We have by definition log(dP/ dQt−1 ) + log
c?t , and so, taking
R εt =? ct ≤
?
?
expectations, we get KL(P, Qt−1 ) + ct µεt ≤ dP ct = ct . Hence,
KL(P, Qt−1 ) ≤ c?t − c?t µεt ≤ (1 + Γε )c?t .
We now show the statement of the theorem. Suppose we are in the lowboosting regime where αt is not clamped. In this case, since log((1 + z)/(1 −
z)) ≥ 2z, we have
νQ
≥ γr ,
αt ≥ t−1
c?t
and it comes from (47)
γr γP c?t
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
.
2
In the high-boosting regime, we have immediately KL(P, Qt ) ≤ KL(P, Qt−1 )−
·
γP c?t . So, letting ρ = min{1, γr /2}, we get under the assumptions of the
theorem KL(P, Qt ) ≤ KL(P, Qt−1 ) − ργP c?t , and WDA yields in addition
through A.1.2,
ργP
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
· KL(P, Qt−1 )
1 + Γε


min{1, γr /2}γP
= 1−
· KL(P, Qt−1 )
1 + Γε


min{2, γr }γP
= 1−
· KL(P, Qt−1 ),
2(1 + Γε )
and we get the statement of the theorem by replacing γr by its expression. 
46

A.1.3

Proof of Theorem 27

The proof of Theorem 27 is essentially a rewriting of the proof of Theorem 19
and Theorem 21, taking into account that we have just samples from distributions to compute the estimates of edges and WLA. We split the proof in
three steps, one that provides an additional Lemma we shall need for the next
steps, one for the non-clamped regime for αt , one for the clamped regime for
αt .
Step.1, We need the additional simple Lemma, which is an exploitation of
basic concentration inequalities [McDiarmid, 1998, Section 3.1].
Lemma 24. For any 0 < δ ≤ 1 and 0 < κ ≤ 1, suppose the weak learner
samples at each iteration t = 1, 2, ..., T , mP times P and mQ times Qt , such
that the following constraints hold:
mP ≥
mQ ≥

1
κ2 γP 2
1
κ2 γQ 2

4T
,
δ
4T
log
.
δ

log

Then there is probability ≥ 1 − δ that for any t = 1, 2, ..., T , the current
estimators µ̂P of µP and ν̂Qt−1 of νQt−1 satisfy:
|µ̂P − µP | ≤ κγP ,
|ν̂Qt−1 − νQt−1 | ≤ κγQ .

(51)
(52)

From now on, we denote as E the proposition that both (51) and (52)
hold for all T iterations, for some 0 < κ ≤ 1 that will be computed later.
We have a slightly weaker version of Lemma 17, straightforward to prove
from Lemma 17.
 1+ν̂

·
Q
Lemma 25. Let αt = 2c1? log 1−ν̂Qt−1 . Then we have under E,
t

EQt−1 exp(αt ct ) ≤

t−1

q

κγQ ν̂Qt−1
1 − ν̂Q2 t−1 + q
.
1 − ν̂Q2 t−1

Lemma 26. Fix any J ≥ 0. Suppose that the two conditions hold:
 
J
,
EQt−1 exp(ct ) ≤ exp
2
J
ν̂Qt−1 ≤
.
1+J
47

(53)
(54)

Then we have under E,
1

EQt−1 exp(ct ) ≤ q
1 − ν̂Q2 t−1

1 + ν̂Qt−1
κγQ
· EQt−1 exp(αt ct + J) · exp
log
2
1 − ν̂Qt−1

!!

Proof. Because the proof mixes the use of ν̂Qt−1 and νQt−1 , we re-sketch the
major lines of the proof from Lemma
 18. First, Jensen’s inequality still yields
?
EQt−1 exp(αt ct ) ≥ exp −αt ct νQt−1 , so we in fact prove

1
q
· exp −αt c?t νQt−1 + J ≥ EQt−1 exp(ct ).
1 − ν̂Q2 t−1
The chain of (in)equalities in (37)–(38) now becomes withe the use of E:

1
q
· exp −αt c?t νQt−1 + J
1 − ν̂Q2 t−1

!
νQ
1
− t−1 log
= expJ + log q
2
1 − ν̂Q2 t−1
!
ν̂Q
1
≥ exp J + log q
− t−1 log
2
1 − ν̂Q2 t−1
!!
1 + ν̂Qt−1
κγQ
log
−
2
1 − ν̂Qt−1

!

1 + ν̂Qt−1 
1 − ν̂Qt−1
!
1 + ν̂Qt−1
1 − ν̂Qt−1

2ν̂Q2 t−1
1 + ν̂Qt−1
κγQ
1
−
log
≥ exp J − ·
4 1 − ν̂Qt−1
2
1 − ν̂Qt−1

!!
.

Provided we have ν̂Qt−1 ≤ J/(1 + J), which is (54), we have similarly to
Lemma 18,
2ν̂Q2 t−1
≤ 2J.
1 − ν̂Qt−1

48

.

Hence, it follows that
!!

1 + ν̂Qt−1
κγQ
1
exp
log
·q
· exp −αt c?t νQt−1 + J
2
1 − ν̂Qt−1
1 − νQ2 t−1


1
≥ exp J − · 2J
4
 
J
,
= exp
2
and so to prove the lemma, we would just need
 
J
EQt−1 exp(ct ) ≤ exp
,
2
which is (53).



Now, instead of (42)–(43), we get


!
1
+
ν̂
1
κγ
Qt−1
Q
log
log EP εt ≤ log q
· EQt−1 exp(αt ct + J) +
2
1
−
ν̂
2
Qt−1
1 − νQt−1




!
1
+
ν̂
E
exp(α
c
)
κγ
Qt−1
Qt−1
t t
Q
log
= log q
· exp(J) +
2
1
−
ν̂
2
Qt−1
1 − νQt−1
!
!
!
1 + ν̂Qt−1
κγQ ν̂Qt−1
γQ
exp(J) +
log
≤ log
1+
1 − ν̂Q2 t−1
4
1 − ν̂Qt−1
!
!
κγQ ν̂Qt−1
1 + ν̂Qt−1
κγQ
= J + log 1 +
+
log
.
1 − ν̂Q2 t−1
2
1 − ν̂Qt−1
We get from (46)
KL(P, Qt ) ≤ KL(P, Qt−1 ) − αt (µP c?t − J − J 0 )

49

(55)

with, because log(1 + x) ≤ x,
κγQ ν̂Qt−1
J = log 1 +
1 − ν̂Q2 t−1

!

1 + ν̂Qt−1
κγQ
+
log
2
1 − ν̂Qt−1

κγQ ν̂Qt−1
= log 1 +
1 − ν̂Q2 t−1

!

2ν̂Qt−1
κγQ
+
log 1 +
2
1 − ν̂Qt−1

0 ·

!

!

κγQ ν̂Qt−1
κγQ ν̂Qt−1
+
2
1 − ν̂Qt−1 1 − ν̂Qt−1
2γQ ν̂Qt−1
≤κ·
1 − ν̂Qt−1
≤

Now, we would like from the PS property and (48) that we have:
ν̂Qt−1 ≤

µP c?t
,
2 + µP c?t

(56)

so
J 0 ≤ κγQ µP c?t ,
and we get from (55),
KL(P, Qt ) ≤ KL(P, Qt−1 ) − αt ((1 − κγQ )µP c?t − J),
and if we fix again J = µP c?t /2, we get this time


1
− κγQ · µP c?t .
KL(P, Qt ) ≤ KL(P, Qt−1 ) − αt ·
2
If we pick κ satisfying


1
κ ≤ min 1,
,
4γQ

(57)

then we are guaranteed 1/2 − κγQ ≥ 1/4 and so


1 + ν̂Qt−1
µP
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
log
,
8
1 − ν̂Qt−1

50

(58)

In the same way as for Theorem 19, we ensure (56) by noting that, since we
are in the case where we do not clamp αt , letting
·

µ̂c?t =

exp(2c?t ) − 1
∈ (0, 1),
exp(2c?t ) + 1

then we again need to ensure νc?t ≤ µP c?t /(2 + µP c?t ), which again yields to
the first PS property.
We are not yet done as we now have to replace µP by its estimate, µ̂P , in
(58). Under E, we obtain


1 + ν̂Qt−1
µ̂P − κγP
,
log
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
8
1 − ν̂Qt−1
and under the (EWLA), we know that µ̂P ≥ γP , so if we also put the constraint
κ ≤ 1/2, then κγP ≤ γP /2 ≤ µ̂P /2 and so:


1 + ν̂Qt−1
µ̂P
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
log
,
16
1 − ν̂Qt−1
as claimed. This ends the proof of Step.2 by remarking two additional facts:
(i) we have not changed the PS properties, and (ii) we have two constraints
over κ (also considering (57)), which can be both satisfied by choosing (since
γQ ≤ 1) κ satisfying
1
(59)
κ≤ .
4
Theorem 27. Suppose EWLA(δ, T ) holds. Then with probability of at least
1 − δ,
(∀t = 1, 2, ..., T )

KL(P, Qt ) ≤ KL(P, Qt−1 ) − ∆t ,

where

 1+ν̂

Qt−1
µ̂P

 16 log 1−ν̂Q
t−1
·

∆t = µ̂ c?

 P2 t + νc2?t · 41 +

in the non-clamped regime,
δ̂t−1
1−νc2?


otherwise.

t

Proof. We proceed in exactly the same way as we did for Theorem 21. We
first remark that Lemma 25 is still valid in this case, so that we still have
1 − νQ νc ?
EQt−1 exp(ct ) ≤ q t−1 t .
1 − νc2?t
51

It is not hard to check that we then keep the exact same derivations as for
Theorem 21, yielding
!
1
δ
t−1
+
,
KL(P, Qt ) ≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·
2 1 − νc2?t
where we have let νQt−1 = (1 + δt−1 )νc?t . Remark that this time, δt−1 is not
necessarily positive since we do not have access to νQt−1 — this may happen
when νQt−1 < ν̂Qt−1 . What we do, to finish up Step.3, is replace δt−1 by the
δ̂t−1 for which we have ν̂Qt−1 = (1 + δ̂t−1 )νc?t , which we are then sure is going
to satisfy δ̂t−1 ≥ 0 under the clamped regime for αt . Under E, we have
νQt−1
−1
νc?t
ν̂Q
γQ
≥ t−1 − 1 − κ ·
νc?t
νc?t
γQ
= δ̂t−1 − κ ·
νc?t

δt−1 =

yielding
!

KL(P, Qt ) ≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·

γQ
δ̂t−1
1
−κ·
+
,
2
?
2
νct (1 − νc?t ) 1 − νc2?t

Suppose we pick κ such that
κ≤

νc?t (1 − νc?t )
.
2

(60)

Since νc?t ∈ [0, 1], we also have
κ≤

νc?t (1 − νc2?t )
2

.

In this case, we obtain, since γQ ≤ 1,
KL(P, Qt ) ≤ KL(P, Qt−1 ) − µP c?t − νc2?t ·

52

!
1
δ̂t−1
+
.
4 1 − νc2?t

Finally, we also know under E that µP c?t ≥ µ̂P c?t −κγP c?t . Under the (EWLA),
we know that µ̂P ≥ γP , so if we again put the constraint κ ≤ 1/2 (satisfied
from (59)), then κγP c?t ≤ γP c?t /2 ≤ µ̂P c?t /2 and so:
!
δ̂
1
µ̂P c?t
t−1
,
− νc2?t ·
+
KL(P, Qt ) ≤ KL(P, Qt−1 ) −
2
4 1 − νc2?t
which ends the proof of Step.3 once we remark that (59) and (60) are both
satisfied if


1 νc?t (1 − νc?t )
κ = min
,
4
2
νc? (1 − νc?t )
= κ? .
= t
2


53

