maxq KBg(p,q) = max

Figure 4: The algorithm has oracle access to either a(γ, 0,m0)-AWL algorithm (see Definition 6) or a(γ,m0)-WL algorithm (see Definition 8). Observe that there are several sources of randomness at play; the weak learning algorithmWi's internal randomness, the booster randomly passing the example toWi (line 5, Algorithm 3), and the randomized prediction (line 2, Algorithm 3).