Optimal Parallelization of Boosting
Authors: Arthur da Cunha
Mikael Møller Høgsgaard
Kasper Green Larsen
Venue: NeurIPS 2024 oral (2024)
Keywords: Learning Theory
Parallel Boosting
PAC-learning
Weak to Strong Learning
Primary area: learning_theory
TL;DR: We settle the parallel complexity of Boosting algorithms that are nearly sample-optimal

Abstract: Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds $p$ and the total parallel work per round $t$.
These works have also presented highly non-trivial parallel algorithms that shed light on different regions of this tradeoff.
Despite these advancements, a significant gap persists between the theoretical lower bounds and the performance of these algorithms across much of the tradeoff space.
In this work, we essentially close this gap by providing both improved lower bounds on the parallel complexity of weak-to-strong learners, and a parallel Boosting algorithm whose performance matches these bounds across the entire $p$ vs. $t$ compromise spectrum, up to logarithmic factors.
Ultimately, this work settles the parallel complexity of Boosting algorithms that are nearly sample-optimal.

Optimal Parallelization of Boosting
Arthur da Cunha
Mikael Møller Høgsgaard
Department of Computer Science Aarhus University dacêcs au.dk
Department Computer Science
Aarhus University hogsgaard&cs.au.
Kasper Green Larsen
Department of Computer Science
Aarhus University larsenøcs. au.dk dk
Abstract
Recent works on the parallel complexity of Boosting have established strong lower bounds on the tradeoff between the number of training rounds p and the total par- allel work per round f. These works have also presented highly non-trivial parallel algorithms that shed light on different regions of this tradeoff. Despite these ad- vancements, significant gap persists between the theoretical lower bounds and the performance of these algorithms across much of the tradeoff space. this work, we essentially close this gap by providing both improved lower bounds on the parallel complexity of weak-to-strong learners, and a parallel Boosting algo- rithm whose performance matches these bounds across the entire vs. compro- mise spectrum, up logarithmic factors. Ultimately, this work settles the parallel complexity of Boosting algorithms that are nearly sample-optimal.
1 Introduction
Boosting is an extremely powerful and elegant idea that allows one to combine multiple inaceu- rate classifiers into highly accurate voting classifier. Algorithms such AdaBoost [Freund and Schapire, 1997] work by iteratively running a base learning algorithm on reweighted versions of the training data produce sequence of classifiers h1, h1,..., hp. After obtaining h4, the weighting of the training data is updated to put larger weights on samples misclassified by h4, and smaller weights on samples classified correctly. This effectively forces the next training iteration focus on points with which the previous classifiers struggle. After sufficiently many rounds, the classifiers hi..... ho are finally combined by taking (weighted) majority vote among their predictions. Many Boosting al- gorithms have been developed over the years, for example Grove and Schuurmans [1998], Rätsch al. [2005]. Servedio [2003], Friedman [2001]. with modern Gradient Boosting [Friedman, 2001] algorithms like XGBoost [Chen and Guestrin, 2016] and LightGBM [Ke et al., 2017] often achiev- ing state-of-the-ar performance on learning tasks while requiring little no data cleaning. See e.g.
the excellent survey by Natekin and Knoll [2013] for more background on Boosting.
While Boosting enjoys many advantages, does have severe drawhack, also highlighted in Natekin and Knoll [2013]: Boosting is completely sequential as each of the consecutive training steps requires the output of previous steps determine the reweighted learning problem. This property is shared by all Boosting algorithms and prohibits the use of computationally heavy training by the base learning algorithm each iteration. For instance, Gradient Boosting algorithms often require hundreds to thousands of iterations to achieve the best accuracy. The crucial point is that even if you have access to thousands of machines for training. there is no way to parallelize the steps of Boosting and distribute the work among the machines (at least beyond the parallelization possible
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

for the base learner). In effect, the training time of the base learning algorithm is directly multiplied by the number of steps of Boosting.
Multiple recent works [Long and Servedio, 2013, Karbasi and Larsen, 2024, Lyu et al., 2024] have studied parallelization of Boosting from theoretical point of view, aiming for an understanding of the inherent tradcoff's between the number of training rounds p and the total parallel work per round These works include both strong lower bounds on the cost parallelization and highly non-trivial parallel Boosting algorithms with provable guarantees on accuracy. Previous studies however leave a significant gap between the performance of the parallel algorithms and the proven lower bounds.
The main contribution of this work is to close this gap by both developing a parallel algorithm with better tradcoff between p and t, as well proving stronger lower bound on this tradcoff. To formally state our improved results and compare them to previous works, we first introduce the theoretical framework under which parallel Boosting is studied.
Weak-to-Strong Learning. Following the previous works Karbasi and Larsen [2024], Lyu et al. [2024], we study parallel Boosting in the theoretical setup of weak-to-strong learning. Weak-to- strong learning introduced by Kearns [1988], Kearns and Valiant [1994] and has inspired the development of the first Boosting algorithms [Schapire, 1990]. In this framework, we consider binary classification over an input domain X' with an unknown target concept X' + {-1,1} assigning labels to samples. A 7-weak learner for e is then a learning algorithm W that for any distribution D over X, when given least some constant my i..dd samples from D, produces with constant probability a hypothesis h with (h) I 1/2 - y. Here LD(h) = Prx-D (h(x) * c(x)]- The goal in weak to-strong learning is then to boost the accuracy of W by invoking it multiple times. Concretely, the aim is to produce a strong learner: A learning algorithm that for any distribution D over X' and any 0 8, E < when given m(e, 5) i.i.d. samples from D, produces with probability at least 1 - 8 a hypothesis h: X' > {-1,1) 1) such that (D(h) S e. We refer to m(e, 8) as the sample complexity of the weak-to-strong learner.
Weak-to-strong learning has been extensively studied over the years, with many proposed algo- rithms, among which AdaBoost [Freund and Schapire, 1997] is perhaps the most famous. If H denotes a hypothesis set such that W always produces hypotheses from H. and if d denotes the VC-dimension of H. then in terms of sample complexity, AdaBoost is known produce strong learner with sample complexity m mAda (5, satisfying
ddn( In
In(1/0)
(E,a(E,
(I)
A22
This can be proved by observing that after / 0(> m) iterations, AdaBoost produces a voting classifier fz) = sign(E; === (x)) with all margins on the training data being ((()). The sample complexity bound then follows by invoking the best known generalization bounds for large margin voting classifiers [Breiman, 1999, Gao and Zhou, 2013]. Here the margin of the voting classifier f on a training sample (sr, e(x)) is defined as c(x) Ei=n (x)) Eisloss- This sample complexity comes within logarithmic factors of the optimal sample complexity morr(e, 8) = (dd((?2)) + l1/1/)/e) obtained e.g. in Larsen and Ritzert [2022].
Parallel Weak-to-Strong Learning. The recent work by Karbasi and Larsen [2024] formalized parallel Boosting in the above weak-to-strong learning setup. Observing that all training happens in the weak learner, they proposed the following definition of parallel Boosting: A weak-to-strong learning algorithm has parallel complexity (p, t) if for p consecutive rounds it queries the weak learner with ł distributions. In each round i, if Di..... ... Dj denotes the distributions queried, the weak learner returns hypotheses hi...., hj E H. such that LD₃ (h)) S 1/2 - y for all j. At the learner outputs hypothesis f: X + (-1, 13. The queries
end of the p rounds, the weak-to-stue made in each round and the final hypothesis of must be computable from the training data as well as all hypotheses hi seen in previous rounds. The motivation for the above definition is that could let one machine/thread handle each of the parallel query distributions in a round.
Since parallel weak-to-strong learning is trivial if we make no requirements on LD(l) for the output f:X- X - 11 (simply output f(x) = 1 for all x E X¹), we from hereon focus on parallel weak- to-strong learners that are near-optimal in terms of the sample complexity and accuracy tradeoff.

---

More formally, from the upper bound side, our goal is to obtain a sample complexity matching at least that of AdaBoost, stated Eq. (1). That rewriting the loss as function of the number of samples we aim for output classifiers f satisfying
(<)))o(d (f/m/d)
(D( (x( o (d [d
In(1/0))
72m
When stating lower bounds the following, we have simplified the expressions by requiring that the expected loss satisfies (p(f) = O(m -001). Note that this is far larger than the upper bounds, except for values of m very close to > 2d. This only makes the lower bounds stronger. We remark that all the lower bounds are more general than this, but focusing on m m-0.01 in this introduction yields the cleanest bounds.
With these definitions, classic AdaBoost and other weak-to-strong learners producing voting clas- sifiers with margins !27)) all have a parallel complexity of (0(r In m), 1): They all need y In rounds to obtain 92()) margins. Karbasí and Larsen [2024] presented the first alter- native tradeoff by giving an algorithm with parallel complexity (1,
Sub- sequent work by Lyu et al. [2024] gave a general tradeoff between and t. When requiring near-optimal accuracy, their tradeoff gives, for any S R S 1/(2>), a parallel complexity of (0(r-2 (mm) / R), exp(O (dRR)) (1(1/)).. The accuracy of both of these algorithms was proved by arguing that they produce a voting classifier with all margins 92
On the lower bound side, Karbasi and Larsen [2024] showed that one three things must hold: Either p min(S(( In m)) exp(S(d))),
z min(exp(S(ddy" exp(exp(((d))) or
p (n((p)) = ((ddn(())) ((m)))()))
Lyu et al. [2024] also presented lower bound that for some parameters is stronger than that of Karbasi and Larsen [2024], and for some is weaker. Concretely, they show that one of the following two must hold: Either p 2 min ?d), 52 2 In m), exp(2((d) (d))), 2 exp(SI(d)). Observe that the constraint on f is only single-exponential
d, whereas the previous lower bound is double- exponential. On the other hand, the lower bound p is essentially stronger by ay factor. Finally, they also give an alternative lower bound for = O()-2), essentially yielding p pln f = 2d)-
Even in light of the previous works, it is still unclear what the true complexity of parallel Boosting is. In fact, the upper and lower bounds only match in the single case where = 12( In m) and = 1, i.e. when standard AdaBoost is optimal.
Our Contributions. In this work, we essentially close the gap between the upper and lower bounds for parallel Boosting. From the upper bound side, we show the following general result.
Let c: X (-1,1} } be an unknown concept, W be q-weak learner for using hypothesis set of VC-dimension d, be an arbitrary distribution. and Dm be training set of size m. For all R E N, Algorithm yields weak-to-strong learner An with parallel complexity (p, 1) for
Theorem 1.1.
In m
In m
== O
and
t= ((dR)
In
R2
8-2
such that, with probability least 1 over S and the randommess of Ar. it holds that
Co(AR(S)) o d dmmm(m) In(m/d) In(1/8)
72m
Observe that this is factor R better than the bound by Lyu al. [2024] in the exponent of Furthermore, if we ignore the In(In(m)/(6~2)) factor, it gives the clean tradeoff
lnt o dl ddlmm
for any p from to 0(> We complement new upper bound by essentially matching lower bound. Here show that
2 mn)

---

Theorem 1.2. There is a universal constant C 2 for which the following holds. For any 0 < Y 1/C, any 2 C, any sample size m 2 C, and any weak-to-strong learner A with parallel complexity (p, 1), there exists an input domain X, distribution DD concept c: x (-1,1) and a n--weak learner W for e using a hypothesis set H. of VC-dimension d such that if expected loss of A over the sample is no more than m. m-0.00 -0.01, then either 2 min min(exp((D(d)) ((7
2In)); or
t 2 exp(exp(((d))) or p lut = 22 lm)..
2
Comparing Theorem 1.2 known upper bounds, first observe that = (2 2 m) corre- sponds to standard AdaBoost and is thus tight. The term p = exp(S((d)) is also near-tight. In particular, given m samples, by Sauer-Shelah, there are only (((m/d)") distinct labellings by H. on the training set. If run AdaBoost, and in every iteration, we check whether a previously obtained hypothesis has advantage under the current weighing, then we make no more than (app(O((n((m///a 22 In m) matches our new upper bound in Theorem 1.1. Thus, only the f. exp(exp((((d)) term does not match any known upper bound.
exp(O(d In(m/dd) /d))
queries to the weak learner (since every returned hypothesis must
be distinct). The p plnt = Q
Other Related Work. Finally, we mention the work by Long and Servedio [2013], which initiated the study of the parallel complexity of Boosting.
their work, they proved that the parallel com- (0(r" In m), regardless of t (they state it p (2y but it is not
plexity (p, t) must satisfy hard to improve by a m factor for loss m -0.01. ). This seems to contradict the upper bounds above. The reason is that their lower bound has restrictions
which query distributions the weak-to-stron learner makes to the weak learner. The upper bounds above thus all circumvent these restrictions. As second restriction, their lower bound instance has VC-dimension that grows with m.
2
Upper Bound
In this section, we discuss our proposed method, Algorithm 1. Here, C, refers universal constant shared among results.
We provide theoretical analysis of the algorithm, showing that it realizes the claims in Theorem 1.1. Our proof goes via the following intermediate theorem:
Theorem 2.1. There exists universal constant On 2 such that for all < < 1/2, R E N,
concept X + (-1.1) 1), and hypothesis set H. C 111 VC-dimession d, Algorithm I given an input training set S Xmm, a 7-weak learner W,
4lm R2R
t t2 16C,dR RIn pR
p
and
produces linear classifier g at Line 21 such that with probability at least 1 over the randomness of Algorithm 1, g(z)c(r) 2 for all x E S.
In Theorem 2.1 and throughout the paper, we define a linear classifier g as linear combination of hypotheses g(x) = > (2);(2)) with Loo = 1. A linear classifier thus corresponds to a voting classifier with coefficients normalized and no sign operation. Observe that the voting classifier f(z) (g))( is correct if and only if c(x)g(()) > O, where c(x) is the correct label of x. Furthermore, c(x) (z) is the margin of the voting classifier f on input x.
Theorem 1.1 follows from Theorem 2.1 via generalization bounds for linear classifiers with large margins. Namely, we apply Breiman's 's min-margin bound:
Theorem 2.2 (Breiman [1999]). Let X + {-1,1} be an unknown concept, H. C. {-1,1) a hypothesis set of VC-dimensioon d and D an arbitrary distribution over X. There is a universal constant C > O such that with probability at least 1 - over set of m samples S ~ DD, it holds for every linear classifier satisfying c(z)g(x) 2 >. for all (z, c(x)) E S that
(s(iig(()) s C. dln(m) In(m/d) + In(1/5)
72m
Thus far, our general strategy mirrors that of previous works: We seek to show that given suitable parameters Algorithm produces linear classifier with margins of order y with good probability.

---

Algorithm 1: Proposed parallel Boosting algorithm
Input TTraining set { c(x1)) )) (Im; ((Em)) y-weak learner W, number of calls to weak learner per round i, number of rounds p
Output: Voting classifier f
1 a In
1/2-7/2 1/2+7/2
2 n C,d/7
3 D) +- m m m
for k 0 1o do
parallel for r - 1 to R do
parallel for j +-
do
Sample TER-r.j ~ D
hERtnr < W( HAR-r f (hantr,1,... hER+nU/R U (--hstt,h....... - -
10
for r +- do
if there exists h HaR+r s.t. CDen. (h") $ 1/2 - 7/2 then
12
haRtr -
Oghtr O
else
15
hRR+T + arbitrary hypothesis from H&R+T
16
aRR+r 0
17
for 1 + 1 to m do
DRR+ +- DaRtr (xxp(p))) (ti))nn))))
18
19
ZER+r L== DaRtr ((p(-asttrc22;)lae
20
DRRtT+1 f DiRtrt1// 2entrti/Ze4tr
E azy (x)
g - x
21 aj
return f: + sign(g(r))
Therefore, this section focuses on the lemmas that describe how, with suitable parameters, Algo- rithm 1 produces classifier with large margins. With these results in hand, the proof of Theorem 2.1 becomes quite straightforward, so we defer it to Appendix B.3.
Algorithm is variant of Lyu et al. [2024, Algorithm 2). The core idea is to use bagging to produce (in parallel) a of hypotheses and use simulate a weak learner. To be more precise, reason in terms of the following definition.
Definition (e-approximation), Given a concept c: X - 1), a hypothesis set H S [1,, and distribution 'D over X, multiset T is E-approximation for D, c, and H if for all h E H. holds that
(kD()) - (h))l
where (h) Unitorrm (h) is the empirical loss of on T. Moreover, we omit the reference to and H. when no confusion seems possible.
Consider a reference distribution Do over a training dataset The bagging part of the method leverages the fact that if a subsample T ~ D is 7/22approximation for Do. then inputting T (with the uniform distribution over it) to a 7-weak learner produces hypothesis à that, besides having advantage
T. also has advantage 7/2 the entire dataset S (relative to Do). Indeed, in this setting, we have that LD, (h) < (r + 2// < 1/2 1/2-3+7/2 = 1/2 7/2.. We can then take as if produced by 7 /22-weak learner queried with (S, Do), and compute a standard Boosting step'. That is, we can simulate a 7/2-weak learner as long as we can provide 2 /2-approximation for the target distribution. The strategy is to have a parallel bagging step in which
distribution D, via
lid we sample T1, Te,..., Tr ~ D and query the 7-weak learner on each T, to obtain hypotheses hi...., h, Then, we search within these hypotheses to sequentially perform R Boosting steps, obtaining distributions D1, D2...., DR. As argued, this approach will succeed whenever we can
Notice that employ tixed learning that assumes worst-case advantage of 7/2.

---

find at least one 7/ app-appproi for each D, among h1, be..... hy. A single parallel round of querying the weak learner thus sufficient for performing R steps of Boosting, effectively reducing p by factor R. Crucially, testing the performance of the returned hypotheses h1,.... h, uses only inferenceeprediicions and no calls to the weak learner.
The challenge is that the distributions D, diverge (exponentially fast) from Do as we progress in the Boosting steps. For the first Boosting step, the following classic result ensures a good probability of obtaining an approximation for Do when sampling from Do itself.
Theorem 2.3 (Li et al. [2001], Talagrand [1994], Vapnik and Chervonenkis [1971]). There is universal constant C
such that for any 0 e, 1, H C {-1,1} of VC-dimension d, and distribution D over X, it holds with probability al least 1 - 5 over a set T ~ DD' that T is an E-approximation for D, c, and H. provided that 2 C((d + In(1/5))/=²).
However, interested in approximations for D, when only have access samples from Do- Lyu et al. [2024] approaches this problem by tracking the "distance" between the distributions in terms of their max- mix-diverge
Doo Do) In(sup (=(=)DD(z)). xEX
(2)
By bounding both Dx (Dr, Do) and D (Du. Dr), the authors can leverage the advanced composi- tion theorem [Dwork et al., 2010] from the differential privacy literature bound the probability of obtaining an approximation for D, when sampling from Do. In turn, this allows them to relate the number of samples and the (sufficiently small) number of Boosting steps R in way that ensures a good probability of success at each step.
Besides setting up the application of advanced composition, the use of the max-divergence also sim- plifies the analysis since its "locality" allows one to bound the divergence between the two distribu- tions via a worst-case study of single entry. However, this approach sacrifices global information, limiting how much we can leverage our understanding of the distributions generated by Boosting algorithms. With that in mind, we instead track the distance between D, and Do in terms of the Kullback-Leibe divergence (KL divergence) [Kullback and Leibler, 1951] between them:
KL(D, || Do) = D))xx) In (x(x)
Do(x))
DEX
Comparing this expression to Eq. (2) reveals that the max-divergence is indeed a worst-case estima- tion of the KL divergence.
The KL divergence also known relative entropy- between two distributions P and Q is always non-negative and equal to zero and only if P Q. Moreover, in our setting, it is always finite due to the following remark.
Remark 1. In the execution Algorithm 1, every distribution Dr, for & E [pRt). has the same support. This must the case since Line 20 always preserves the support of D1.
On the other hand, the KL divergence is not a proper metric it is not symmetric and it does not satisfy the triangle inequality, unlike the max- max-divergence. This introduces number of difficulties in bounding the divergence between Do and D,,. Overcoming these challenges requires a deeper and highly novel analysis. Our results reveal that the KL divergence captures particularly well the behavior of our Boosting algorithm. We remark that we are the first to relate KL divergence and Boosting, see e.g. Schapire and Freund [2012, Chapter 8 and the references therein], yet we make several new contributions to this connection.
To study the probability of obtaining a 7//2 7/22-approximation for D, when sampling from Do. rather than using advanced composition, employ the duality formula for variational inference [Donsker and Varadhan, 1975]- alsoo known as Gibbs variational principle, or Donsker- Varadhan forauhaanformulaa to estimate such probability in terms of KL,(D, || Do).
Lemma 4.6 of Lyu et al. [2024].
*We only need P to be absolutely continuous with respect to Q: i.c., that for any event A, we have P(A) = 0 whenever Q(A) = 0. We express our results in terms of identical supports for the sake of simplicity as they be readily generalized to only require absolute continuity.

---

Lemma 2.4 (Duality formula"). Given finite probability spaces (2, P) and (Ω. FFQ),. if P and Q have the same support, then for any real-valued random variable X on (S2, F, P) we have that
In E[ Eo(x] - KLLQ || P).
(3)
Lemma 2.4 allows to prove that if KL(D, Do) is sufficiently small, then the probability of obtaining a 7/ /22aaprroximation for D, when sampling from Do is sufficiently large. Namely, we prove the following.
Lemma 2.5. There exists universal constant Cu 2 1 for which the following holds. Given O < < 1/2, R. E N, concept X {-1,1}, and hypothesis set Ht _ {-1,1] VC-dimension d, let D and D be distributions over [m] and G E [m]] be the family of /tppp-aaproiimiionn/ for D, c, and H. If D and D have the same support and
KL(D $
then for all 2 C. d/r² it holds that
(TE [] exp(-16C,,d1) T~Dn
Pr
Proof sketch. Our argument resembles a proof of the Chernoff bound: After taking exponentials
on both sides of Eq. (3), exploit the generality of Lemma 2.4 by defining the random variable X: T + (rggg and later carefully choosing A. We then note that Theorem 2.3 ensures that X has high expectation for T D Setting À to leverage this fact, we obtain lower bound the expectation of X relative to T D", yielding the thesis.
L
We defer the detailed proof to Appendix B.I.
With Lemma 2.5 in hand, recall that our general goal show that, with high probability, the linear classifier produced by Algorithm satisfies that c(x)g(x) = 52(7) for all x E S. Standard tech- niques allow us to further reduce this goal that of showing that the product of the normalization factors, II Ze, is sufficiently small. Accordingly, in our next lemma, we bound the number of samples needed in the bagging step to obtain small product of the normalization factors produced by the Boosting steps.
Here, the analysis in terms of the KL divergence delivers clear insight into the problem, revealing an interesting trichotomy: if KL(D, Db) small, Lemma 2.5 yields the result; on the other hand, if D, has diverged too far from Do. then either the algorithm has already made enough progress for us to skip a step, or the negation of some hypothesis used previous step has sufficient advantage relative to the distribution at hand. Formally, we prove the following.
Lemma 2.6. There exists universal constant C. 2 1 such that for all R E < 1/2, and --wakk learner W using hypothesis set H C {-1,1} with VC-dimension d. ift R exp(160, dR) (n(R/5). then with probability at least the hypotheses hgR+1..... h&R+R obtained by Algorithm 1 induce normalization factors ZER+I,... ZER+R such that
R II
ZeR+r < <exp(->?R/2).
Proof sketch. We assume for simplicity that = 0 and argue by induction on R' E [R]. After handling the somewhat intricate stochastic relationships of the problem, leverage the simple
'Corollary of, e.g., Dembo and Zeitouni [1998, Lemma 6.2.13] or Lee [2022, Theorem 2.1]. Presented here weaker form for the sake of simplicity.
7

---

remark that (L D 0 to reveal the following telescopic decomposition:
Kl,(Dæ
Di) RT ! D1) KI,D DR)
= =K R Di) K D2)
+ (L D2) KL(D D3)
KL(DRR R DR-1) KL(DR( R Dw)
R2
KL(DR D.) - KL(D Dr+1).
Moreover, given r E {I...., R' 1}.
m
(1)
( (1) De
KL(DR D,) KI,(DR D,+1)=
Σ (1)
Σ
D,(1)
(1+1(1)
i=1
(=1
Dr+1(1)
Σ (
In
Di
In Z,
D Dæ ((i)),,
Altogether, we obtain that
R-11 a (=(()(())
T
KL(D D1) = In II Z,
Now, if KL(DR | Di) is small (at most 4y² Lemma 2.5 ensures that with sufficient probability there exists a 7/2 2/2-approximation for DR within TR. Tw, Rt/R yielding the induction step
(by Claim 1). Otherwise, if KL(DR || Di) is large, then either (i) the term In I1 Z, large enough for us conclude that II 12'-1 Zy is already less than exp(->2 Rt' R2/2) /2) and we can skip the step; (ii) the term DR11 0r -=1 De (x.( is sufficiently large to imply the existence h² E (-h,,.... - satisfying that
m
Σ DR (1)c(2)) 7.
which implies that such h" has margin at least y with respect D and we conclude the induction step as before.
We defer the detailed proof to Appendix B.2.
3 Overview of the Lower Bound
In this section, we provide an overview of the main ideas behind our improved lower bound. The details available in Appendix C.
Our lower bound proof is inspired by and builds upon the work of Lyu et al. [2024], which we now summarize. Similarly to Karbasi and Larsen [2024], they consider input domain X [2m], where m denotes the number of training samples available for a weak-to-strong learner AA with parallel complexity (p, t). In their construction, they consider uniform random concept X - {-1,1} and give randomized construction a weak learner. Proving a lower bound on the expected error of AA under this random choice of concept and weak learner implies, by averaging, the existence of a deterministic choice of concept and weak learner for which A has at least the same error.
The weak learner is constructed by drawing a random hypothesis set H. using inspiration from the so-called coin problem. In the coin problem, observe p independent outcomes of a biased coin

---

and the goal is to determine the direction of the bias. If coin has bias of B, then upon seeing outcomes of the coin, any algorithm for guessing the bias of the coin is wrong with probability at least exp(- O (3))))) Now to connect this to parallel Boosting, Lyu et al. construct H. by adding e as well as p random hypotheses hj....; hp to H. Each hypothesis h, has each h; chosen independently with (z) c(x) holding with probability 1/2 2y- The weak learner W now processes a query distribution D by returning the first hypothesis h, with advantage y under D. If no such hypothesis exists, it instead returns c. The key observation is that if W is never forced to return c, then the only information A has about c(xr) for each a not in the training data (which is at least half of all since [X| 2m), is the outcomes of up to p coin tosses that are 2y biased towards c(z). Thus, the expected error becomes exp( O()²p)). For this to be smaller than m 0.01 then requires p S0 In m) claimed in their lower bound.
The last step of their proof, then to argue that W rarely has to return e upon a query. The idea here is to show that in the ith parallel round, W can use h; to answer all queries, provided that t is small enough. This is done by observing that for any query distribution D that is independent of h, the expected loss satisfies En, [Co[[, (h.)] = 1/2 - -2y due to the bias. Using inspiration from Karbasi and Larsen [2024], they then show that for sufficiently "well-spread" queries D, the loss of h; under D is highly concentrated around its expectation (over the random choice of h.) and thus h; may simultaneously answer all (up to) t well-spread queries in round i. To handle "concentrated" queries, i.e., query distribution with most of the weight on few æ, they also use ideas from Karbasi and Larsen [2024] to argue that if we add 20(d) uniform random hypotheses to H. then these may be used to answer all concentrated queries.
Note that the proof crucially relies on h, being independent of the queries in the ith round. Here the key idea is that if W can answer all the queries in round using h,, then h.+1,..., hp are independent of any queries the weak-to-strong learner makes in round i + 1.
In our improved lower bound, we observe that the expected error of exp(- (p))p) is much larger than m 0.001 for small p. That is, the previous proof is in some sense showing something much too strong when trying understand the tradeoff between p and t. What this gives us, is that we can afford to make the coins/hypotheses h; much more biased towards c when p is small. Concretely, we can let the bias be as large as 3 = ((vIn(m)/p) which may be much larger than 27. This, in turn, makes it significantly more likely that h; can answer an independently chosen query distribution D. In this way, the same h, may answer a much larger number of queries L, resulting in a tight tradeoff between the parameters. As a second contribution, we also find a better way of analyzing this lower bound instance, improving one term in the lower bound on from exp(I(()) to exp(exp(d)). We refer the reader to the full proof for details.
4 Conclusion
In this paper, we have addressed the parallelization of Boosting algorithms. By establishing both improved lower bounds and an essentially optimal algorithm, we have effectively closed the gap between theoretical lower bounds and performance guarantees across the entire tradeoff spectrum between the number of training rounds and the parallel work per round.
Given that, we believe future work may focus on better understanding the applicability of the theo- retical tools developed here to other settings since some lemmas obtained seem quite general. They may aid, for example, in investigating to which extent the post-processing of hypotheses obtained in the bagging step can improve the complexity of parallel Boosting algorithms, which remains as an interesting research direction.
Acknowledgments and Disclosure of Funding
This research is co-funded by the European Union (ERC, TUCLA, 101125203) and Independent Research Fund Denmark (DFF) Sapere Aude Research Leader Grant No. 9064-00068B. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

---

References
Yoav Freund and Robert E Schapire. A decision-thcoretic generalization on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139) 1997.
Adam J Grove and Dale Schuurmans. Boosting in the limit: Maximizing the margin of learned ensembles. In AAAI/IAA,, pages 692-699, 1998.
Gunnar Rätsch, Manfred K Warmuth, and John Shawe- TaalerTaylor. Efficient margin maximizing with boosting. Journal of Machine Learning Research, 6(12), 2005.
Rocco A. Servedio. Smooth boosting and learning with malicious noise. J. Mach. Learn. Res., (null):633-6448 dec 2003, ISSN 1532-4435, doi: 10.162/15524334779333777 URL https: //doi. org/ 10. 1tt.111///52244477788880800
Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5): 189 1232, 2001.
Tianqi Chen and Carlos Guestrin. Xgboost: scalable tree boosting system. In KDD, pages 785-
794. ACM, 2016. ISBN 978 177-1-4503-4232-2
Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie-
Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. In NIPS, 2017.
Alexey Natekin and Alois Knoll. Gradient boosting machines, a tutorial. Frontiers in Neurorobotics, 7, 2013. ISSN 1662-5218.
Philip M. Long and Rocco A. Servedio. Algorithms and hardness results for parallel large margin learning. J. Mach. Learn. Res., (4(1)3105--3128, jan 2013. ISSN 1532-4435.
Amin Karbasi and Kasper Green Larsen. The impossibility of parallelizing boosting. In Claire Vernade and Daniel Hsu, editors, Proceedings of The 35th International Conference Algorith- mic Learning Theory, volume 237 of Proceedings of Machine Learning Research, pages 635-653. PMLR, 25-28 Feb 2024. URL https: /ttttps://procee http://pooeeeeeneeee/ee/eeee mlr ptw.sappee////eee ppress/v237/ /arbaaarbaaasaa 24a html.
Xin Lyu, Hongxun Wu, and Junzhao Yang. The cost of parallelizing boosting. In David Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 3140-3155. SIAM, 2024. doi: 10.1137/1. 9781611977912.111 URL httpt:://////tt..ttt /doi. http:/::/ddoo////ee/eeeee
91117771.978111197799922 112.
Michael Kearns. Learning boolean formulae or finite automata is as hard as factoring. Technical Report TR- 14-14-88 Harvard University Aikem Computation Laboratory, 1988.
Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994.
Robert E Schapire. The strength of weak learnability. Machine learning, 5(2):197-227, 1990.
Leo Breiman. Prediction games and arcing algorithms. Neural Computation, 11(7):1493- doi: 10. (0.11666209977669900066666 089976699300016006.
1517, 1999.
URL https://doi.org// 1162/
Wei Gao and Zui-Hua Zhou. On the doubt about margin explanation of boosting. Artif. Intell., 203: 1-18, 2013.
Kasper Green Larsen and Martin Ritzert. Optimal weak to strong learning. In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors. Ad- vances in Neural Information Processing Systems 35: Annual Conference on Neural Informa- tion Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28 De- httpc/pape_fffleppeeeeeeeeeee /22hhh/h022/ashh hashh/
cember 2022, 2022. URL http:/ http::::/aapppss....e -btara---ttataaaaa--rreeeee
html.
Yi Li, Philip M. Long, and Aravind Srinivasan. Improved bounds on the sample complexity of learning. Journal of Computer and System Sciences, 62(3):516-577, 2001. doi: 10.1006SISSS. 2000.1741. URL https:://dd org/ 10. 1006 (/006/ccss jass 2000 1741.
10

---

Michel Talagrand. Sharper bounds for gaussian and empirical processes. The Annals of Probability, pages 28-76, 1994.
Vladimir N Vapnik and Ya Chervonenkis. the uniform convergence relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51th Anmual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 51-60. IEEE Computer Society, 2010. doi: 10.1109/FOCS. 2010.12. URL https :
///i/iioooo org/ ///g/////// 10. 1109/F0CSS 20100..001.... 2010.12.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathe- matical statistics, 22(1):79-86, 1951.
Robert Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 05 2012. ISBN 9780262301 183. doi: 037551/mitpres/8221..000 10. 100.7551/mittpress/88233 001.0001.
URL ttttps://dol. / org/
Monroe D Donsker and SRS386024 Varadhan. Asymptotic evaluation of certain markov process expectations for large time, and ii. Communications on Pure and Applied Mathematics, 28(1-2): 279-301, 1975.
Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications. Springer, 1998. ISBN 978- 978-1-4612-5332-4 doi: 10.1007/978-14411255222 URL https://doi http:///doi..r//110// org/10. 10.
0007/978-1-4612-55
Se Yoon Lee. Gibbs sampler and coordinate ascent variational inference: A set-theoretical review. Communications Statistics Caaisty and Methods, 51(6):1549-155 1568, 2022.

---

A Auxiliary Results
In this section we state and proof claims utilized our argument. The arguments behind those are fairly standard, so they are not explicitly stated in the main text.
Claim 1. Let & E N and 0 < < 1/2. If a hypothesis he has advantage "it satisfying LD, (he) = 1/2 1/2-7e- ve - 1/2 7/2 and og a, then
Ze S -
Proof. It holds that
Y1
Ze
Σ
Dz(1) ex()))x((
De(i)e-a
E
Deli)e
T-7
1+7
2 78
+
Vi-7
1 7
1/2 + 7
1/2 - Ve
V(1+7) 7)
1+7
1 1-7
1 - 2y. - Mt
V1-
1 1-72
Finally, since "/ 2 7/2 and 7 E (0, 1/2), and, thus, 1 7-2 > 0, we have that
1
27. Ye
1 1-22
1.
72 1 72
Claim 2. Algorithm produces linear classifier g whose exponential loss satisfies
PR
pR
Σ exp
c(x;; Σ (,,)
= m
II
Z
j=1
j=1
Proof. It suffices to consider last distribution DRR+1 produced by the algorithm. holds that
m
D (1)
(as DpR+1 a distribution)
exp( (pRc(Es)hpRRt1)
Σ DiR(i)
(by Line 20)
ZpR
pR
exp( a
Σ
(1(
(by further unrolling the Djs)
Z;
i=1
i=1
m
exp(-c((xt (())) Een oz h (xi))
(as Dj is uniform)
m ! Z₁
B Detailed Proofs
In this section, provide full proofs for the results from Section For convenience, we provide copies of the statements before each proof.
12

---

B.1 Proof of Lemma 2.5
Lemma 2.5. There exists universal constant C. Z 1 for which the following holds. Given 0 < < 1/2, R, m E N. concept X' + {-1,1}. and hypothesis set H. - {-1,1}} of VC-dimension d, let D and D be distributions over [m] and g E [m]" be the family of //pp/=aappoxiiiiionn//// for D, c, and H. If D and D have the same support and
KL I| 5 R,
then for all Ca d/n² it holds that
Pr TwDn
TTE 2 cxp(- (116
Proof. Let A E R50 (to be chosen later) and X; [m] {0, be the random variable given by
( - (T
Since D and D have the same support, so do 1 and D Thus, taking the exponential of both sides of Eq. (3), Lemma 2.4 yields that
exp(- exp(-KI(nD"I) 1T)) + Ep (X] S EDn [c>].
(4)
We have that
En X = X- Pr [T g). T~D"
(5)
Moreover,
E Dz [ex]
ETwDo [et 1 (TE)) + 1 [
BTwDa [et ((TE)) + (reg))
= +1+ (e* - -1) [
=1 (e) -1) 1) Pr T g).
T~
Applying Eqs. (5) and (6) to Eq. (4), obtain that
exp - (LL(D" D²) + x Pr TE gi) $1+ - -1 Pr Twpr
T g]
Twhr
and, thus,
KL(D") || Dm) + Pr TE -1
exp
Pr 2 D~
1
for any 0. Choosing
KL(D" D + ln2
PrT=D= T E
we obtain that
T 1 Pr
Twhi
ed -1 >
Now, by Theorem 2.3 (using 8 = 1/2), there exists constant Cn such that having
n 2 Cn 72
ensures that
T g 2 2"
T~D"
13

---

Also, since, by hypothesis, KL(D D) - 4 R. we have that
KL(D" D*) n kL D)
I 4CndR.
Applying to Eq. (7), we conclude that
4Cnd In 2
Pr TwDn
Teg exp
1/2
cxp(-16C,,1p)
B.2 Proof of Lemma 2.6
Lemma 2.6. There exists universal constant C, such that for all E, L, 1/2, and 7-weak n-wak learner W using a hypothesis set H. S [-1,1}2 with VC-dimension d. ift 2 R. exp(16C,dR)) (n(R/5), then with probability at least 5 the hypotheses hER+1..... hgR+R obtained by Algorithm I induce normalization factors factors ZkR+1..... ZER+R such that
II
ZaR+r < <exp(->>
r=1
Proof. Assume, for simplicity, that 0. Letting
R'
ER II Z, < exp( exp(->21(/22)
we will show that for all R' E [R] it holds that
Pr[ER/ ,
8/12.
(8)
The thesis then follows by noting that
Pr[& 0.. n En]
Pr Ei,..., Ey-1]
(by the chain rule)
r=1
2
1
(by Eq. (8))
R
2 R
(by Bernoulli's inequality)
R
Let DDw [m]" R be the family of 7/2 /ppappproxsstssoon for D and recall that if T G then any h = W(T, Uniform(T") satisfies LD (h) < 1/2 7/2. Therefore, the existence of TR 9 g. for some j* [t/R], implies that h HR has margin at least 7/2 relative to DR. Hence, Algorithm 1 can select h at Line 11, setting a = so that, by Claim 1, we have that ZR S exp(->2/2)
Now notice that, by the law of total probability,
Pr En n E.
Pr KL R. || Di) R n E.] Pr ER E, KL(DR Di) < 47
Pr KL(D D1) > 4 [ Pr Ew nI KL(D D1) 47
14

---

We will show that, conditioned on - E,, if Di) to argue that with probability least 8/ there exists a 7/ /22aaprrxximation for Re within T Tw.,,..... T Rt a/R, and that Ev follows. On the other hand, if KT.(Drr || D1) > 4y R, we shall prove that E necessarily holds. Under those two claims, Eq. (9) yields that
I 442R, Di) we can leverage Lemma 2.5
Pr Pr[En/ | E.
Pr Pr[KL(DRi D1) - 47 n - E,
1
R
+ +Pr[KT(DIr | D1) 47 R
n - Eg
.1
Pr [I. || DI) - 4 -
&
(1 R
+ +Pr[KT D1) 472
- &
(1- d'
R
8
R
which, argued, concludes the proof.
To proceed, we ought to consider the relationships between the random variables involved. do so, for E [R] let T, (T........, TT.r/ Notice that D R is itself random and determined by D1, and ...... T --
For the first part, let D, and Ti...., TR' be realizations of Dj and ,,....,T - such that n holds and KL(DR' || D1) 4y2 Notice that if there exists 7/2-approximation for DR within TR R. then we can choose some hg E HR R with advantage at least 7/2 so that
R'
R'
II r=1
Z,
Zre
II
Zr
r=1
< ZR' exp( 1 11/2)
(as we condition on -
I
R2/2)
(by Claim 1)
and, thus, & follows. That is,
Pr En in''-e,,, KL(DRe || Di) < 4,2
Pr Twtajn T
[ [1/R), TR g
lid
(10)
Finally, since by Remark the distributions Dr and Dj must have the same support, and we assume that KL(DR || Di) < 4y² R, Lemma 2.5 ensures that
Pr (T E 9Dwl 2 exp(-16C,dR). T~D
Therefore,
( Pr TwDD
t/8
Pr
Vij E [//)) TRi 9nxl
T $ gD
(by IIDness)
Tw T Df
id
$ (1 - --x-expp-200 1ep(-16C,,dB)) dR)
s exp (RR expl exp(-16C,ddT))
8
< R
where the second inequality follows since + et for all R and the last from the hypothesis that 2 R. exp(16C,,dR) In(R/)). Considering the complementary event and applying Eq. (10), obtain that E holds with probability least 1 8/R.
For the second part, consider instead D, and Tı,... TR- realizations of D, and T TI,..., T R-1
such that -1g E, holds and
2 < <KL || D.).
(11)
15

---

and argue that Er necessarily follows.
Observe that
KL(DR( || Di) =KL Di) ( || DR)
= <L || D1) KL(DR( || D2)
KL(DR D2) KL(DR D3)
+...
+ +KL(DR) || DR-1) KL(DR( DR)
R1-1
=
Σ
KL(DR/ D2) KL(D |I Dr+1).
(12)
==1
Moreover, given E (1,..., R' 1}
Σ (1) In Dir
m
m
Die (t)
KL(DR || D,) KL(DR( D++1)
Σ
(1) In
D1
(1)
DR (i) In D1+1(1)
D,
exp(-a,
Σ 1=1
DR (i) In
2r
m Σ 1=1
In Z,
De c(x()))))))
Applying it to Eqs. (11) and (12) yields that
R
R1
m
4 < KL(DR( D1) = - In
II
Σ ar Σ (1))))()))
r=1
Thus, either
R'
2
In
Z,
(13)
or
R²-1
4r2R
(14)
2
We proceed to analyze each case. Eq. (13) holds, then
R'-1
II Z, 2xp(-22211
< exp(->2
and Ex follows by noting that Z -1-2-1
1 regardless of the outcome of Line 11 so I1 2r S
On the other hand, if Eq. (14) holds, then, letting R = (r E [T 11'0-11 ar + 0}.
2- R
<
Dre (1)
r=1
1=1
= Σ a
(1)())())))
FER
i=1
16

---

Since [R] - R, we obtain that
E Σ1>
> 27²
Σ
R
PER
so that there exists ht hh R} such that
m Σ (x))
27²
(15)
a
Moreover, from the definition of a,
1/2 7/2
a In
1/2 - 7/2
In 1 2
2
1-7
27,
(16)
where the last inequality holds for any (0, 1/2). Applying it to Eq. (15) yields that
27
(i)c((;))))(
27
2 %
thus LD (h²) < 1/2 7/2 and, as before, Exr follows by Claim and the conditioning on 0 RR--',,. E,
B.3 Proof of Theorem 2.1
Theorem 2.1. There exists universal constant C2 2 such that for all < < 1/2, R E N, concept X - (-1.1,, and hypothesis H C 11, of VC-dimension d, Algorithm I given an input training set Xm, a r-weak learner W,
4lm m
t 1 160,, Rlnn pR
p z
and
R2
produces linear classifier g at Line such that with probability at least 5 over the randomness of Algorithm 1, g(z)c(x)) 2 7/8 for all E S.
Proof. Let h E (0, 1. p-11, Applying Lemma 2.6 with failure probability 5/p, we obtain that with probability at least 5/p.
R
II
ZER+o < exp(->><R/2.
Thus, by the union bound, the probability that this holds for all & E (0, 10....... p-11) 1} is at least 1 - 5. Under this event, we have that
m
RR
pR
Σ exp
-e(xx) Σ (,
= m
Z
(by Claim 2)
j=l
j=1
p-1 R
ZER+T
p-1
< m
cxp( R222
k=
exp( (R2PR(2).
(17)
17

---

Now, let 0 2 O. If c(z)g(z) < 0, then, by the definition of at Line 21, it must hold that
c(x) ΣØ (z)((a) < شز= a,d, thus the difference Σ a, c(t) P at azyy(4) is strictly positive. Taking the exponential, we obtain that, for all S.
(<()))(=)<0) 1
DR a, c(x)
RR
Σ
Σ
< exp
j=1
I exp(pRaO))xxp
-c(x) Σ asp)(t))
(as 0j S a)
Therefore,
m
m
pi
1 (c())))(s))C)) < exp(pRad)
Σ
exp
-d(x;) Σ
a a, (ai)
j=1
Applying Eq. (17), we obtain that
(c) < m mexp(pRad))xpp
=mexpppR(aa - -
Finally, since 0 S a S 2y (see Eq. (16)), we have that, for 0 < $ 7/8, al 72/2 / < 27 7/8 72
$ 2/1
and thus
(cx)g())))//)) < mmeppp-1a (
S m
(as p 2 4Rt 4 Inm))
and we can conclude that all points have a margin greater than 7/8.
C Lower Bound
In this section, we prove Theorem 1.2. Theorem 1.2 a consequence of the following Theorem C.2. Before we state Theorem C.2 we will: state the assumptions that we make in the lower bound for a learning algorithm A with parallel complexity (p, t), the definition of 7-weak learner in this section and describe the hard instance. For this let X + {-1, denote labelling function. Furthermore, throughout Appendix C Csize = C, 2 1, Chias == C, 2 and Closs := C 2 denote the same universal constants.
Assumption C.1. Let Q' with Q < be the queries made by a learning algorithm AA with parallel complexity (p, during the äth round. We assume that query Q E Q' for i 1,..., . and on the form (S). (S where the elements in St. are contained in S, and that j 1,, 1,...,A /
the distribution Dj has support ) C (()))....... ())))) Furthermore, we assume Q! only depends on the given sample S E xm and the sample labels c(S) where c(S); c(S.). and that Q' for i = 2, .....P only depends on the label sample S, c(S) and the previous queries and the responses to these queries.
We now clarify what we mean by a weak learner in this section.
Definition 2. A 7-weak learner W acting hypothesis set H. takes as input (S, c(S). D). where S x X' c(S): h = (S D) is such that E, (()) # c(i) < 1/2 7
c(S)) and supp( D) C S2.......). The output of
18

---

We now define the hard instance which is the same construction as used in Lyu et al. [2024] (which was inspired by Karbasi and Larsen [2024]). For d N. samples size m, and < ? aC% consider the following hard instance
1. The universe X' we take to be [2m].
The distribution D we will use on [2m] will be the uniform distribution U over [2m]. going to is the uniform random concept {-1, 1, 1mmm i.c.
3. The random concept that all the labels of с are i.i.d. and Pra(e(i) = 1] = 1/2 for i ,....,m..
The random hypothesis the random concept c, thus we will denote it Hp.c.R. We will see Hp.e, R as matrix where the rows are the hypothesis so vectors of length 2mm, where the entry specifies the prediction the hypothesis makes on element E [2m]. To define H H.p...R R we first define two random matrices Hy and He. H. is a random matrix consisting R |exp (C,d)] rows, where the rows in H, are i.d. with distribution random matrix with R rows, where the rows in Hhe are i.id. distribution b [-1, 1) meaning the entries of b are independent and has distribution P [b( * c(i)
will depend on the number of parallel rounds p. scalar N, and
{-1, 2 (r has i..d. entries Pr (i.1f-111)am [r(1) 1] 1/2).. He is
1/2 1 C&y (so Coy biased towards the sign of c). We now let H., H e....., H. He denote i..d.
copies of respectively H. and He. and set H....R to be these i.idd. copies stack on top of each other and H. H....I U to be the random matrix which first rows are Hp... and its last row
H
H
Hpp..
Hp....FF =
Hp.c.R Uc=
H 1H
5. The algorithm W which given matrix/hypothesis set M E R x Rm (where M., denotes the ith row of M) is the following algorithm W(M).
Algorithm 2: W(M)
Input :Triple (S, c(S), D) where [2m]", c(S); = c(S:) and probability distribution D with supp(D) C {S1, S2,...,
Output: Hypothesis
Mr. for some .,..., such that:
Σ, (() # c(i)) < 1/2 7.
1 for i E [2] do
if Σ, (M,, # c()) < 112 // Notice that W doesn't know e but can calculate this quantity using the information in (S,c(S), which is given as input. then return M...
5 return M1..
We notice that with this construction, we have that Hpp..Rl < R [exp (C,d)]+RB) and W(H R c) a weak learner since it either finds a row in Hp..R. with enror less than 1/2 - for query or outputs e which has 0 error for any query this follows by the Assumption C. that the learning algorithm given (S, cSS) make queries which is consistent with
With these definitions and notation in place, we now state Theorem C.2, which Theorem 1.2 is consequence of.
Theorem C.2. For d E N, E N, margin 0 < < .C.. R.p.t E N, universe [2m), U the uniform distribution [2m], and the uniform concept on [2m] any learning algorithm A with parallel complexity (p,t), given labelled training set cSS), where ~ Um", and query access W(H. Uc) have that
Ess., (.E. (A(S W(Hppee Uc)))]
exp( 2 (1 exexp (- (-mexpl -mxppp-ppCC (expp(-C,Cy2RR)) exp (-Rd)
4C;
8C:
19

---

We now restate and give the proof of Theorem 1.2.
Theorem 1.2. There is a universal constant C 2 for which the following holds. For any 0 < Y < 1/C, any d 2 C, any sample size m Z C. and any weak-to-strong learner A with parallel complexity (p, 1), there exists an input domain X, a distribution DD a concept c: X ++ {-1,11 J. and a y-weak learner W for e using a hypothesis set H. of VC-dimension d such that if expected loss of A over the sample is no more than m 0.01 then either 2 (ex)((((d)) Imm]]. or
t z exp(exp(((d))), or p lnt 12(7 3d m)
Proof of Theorem 1.2. Fix d 2 1, sample size 2 (e80C;) 100 margin 0 < y IC2 P such that p S min exp(d/S), (m /80C;) S exp(exp(d)/S) 8) and p In(!) S diu(( 0.01, /80C;)
1
We now
20
BC;
want to invoke Theorem C.2 with different values of R depending on the value of p. We consider 2 cases. Firstly, the case
In (m /80Ci) 2C,02h² [exp(d)
In (m /8001/8
S S
20,0
In this case one can choose R N such that 1 < R < [exp(d)] and
In (m 0.01 /8OC1)
In (m 0.01 /80C1)
S S
R
2CIC)+
Let now R be such. We now invoke Theorem C.2 with the above parameters and get
HI c(S), W(H,p.c.H Uc)))]
(18)
IV exp(- Rp) (1- (1-cxp (- _mxep(-C.CC-PP
)
pt cxp cxp (-Rd)
40
8C,
We now bound the individual terms on the right-hand side of Eq. (18). Firstly, since
1n /800:)
In(m2.01/8000
p S 2C
S
C.C.
get that exp( -0,(-C
20m 0.01 which further implies that
4C;
m -mexp(-C.Cs
< <exp(-10m S -10
exp
8Ci
d 21n(m=001/80)
We further notice that for R as above we have that p pln(exp(Rd/4)) >
This implies
80,0772
that t S cxp(Rd/4), since else we would have > exp(Rd/4) and p pln(t) > p exxp Rd/4) 2 d dil ( 0.00 /suC;) which is a contradiction with our assumption that pln(t)= < 80,0877
d'ln d'lnmm 0.01 /sUCi) Since 80,077
we also assumed that p I exp(d/ (d//)) we have that pt S exp(d/8+Rd/4 Combining this with R > 1 and d 2 1 we have that pt exp (Rd)= < exp (Rd/2) e-. Combining the above observations
get that the right-hand side of Eq. (18) is at least
Es.. (A(S, W(H Uc))) 2 20m 0.01 (1 e1-e- -10
-10 -) -10---1 2 m 0.01
Now in the case that
In 0m000 /80C:)
p < 20,037² [exp(d)]
(19)
we choose R lexp(d)). Invoking Theorem C.2 again give use the expression in Eq. (18) (with the parameter R = /exp(d) now) and we again proceed to lower bound the rinht-hand
side of Eq. (18). First we observe that by the upper bound on p in Eq. (19), R = /exp(d) and
exp(-a/2) 2 (-p) for x 2 1 we get that e Rp)
> expí In in(1n2 n.00 /80C. )/2) >
4C 20m 20m.-0011 which further implies that exp exp( C Rp)
4C;
S 10 Now since [x| 2 x/2
8Ci
for z 2 1, R [exp(d) and we assumed that t < exp(exp(d)) (8/ and exp(d/8) we get that
20

---

pt ex) I exp (exp(d)/8 8 + d/8 exxp(d)/2) I exp (-d (-dexp(d)/4) S c 0//4 Combining the above observations we get that the right-hand side of Eq. (18) is least
(A
WHp....R Uc))]] 2 20m 00.01
(1 (1- e e e-0/4 e/4
m -0.01
Thus, for any of the above parameters d, m. Y.P. in the specified parameter ranges, we have that the expected loss of A over S, c, H.,.eR is at least m 0.01 so there exists concept c and hypothesis H such that the expected loss of A over S is at least m -0.01, Furthermore, if A were a random algorithm Yao's minimax principle would give the same lower bound for the expected loss over A and S as the above bound holds for any deterministic A.
Now as remarked on before the proof the size of the hypothesis set Hp,., is at most (Hp... S R Texp (C,d)] + Rp, see Item 4. Combining this with us in the above arguments having p S exp(d/8), R I cxp(d) we conclude that 17 U cl I exp(Cd/2) for Ò large enough. Thus, we get at bound of logg H U cl) < (exx(((ddd2))
< Ed which is also an upper bound of the VC-dimension of H. U c. Now redoing the above arguments with d scaled by 1/C we get that the VC-dimension of iUcis upper bounded by d and the same expected loss of m -0.01, The constraints given in the start of the proof with this rescaling of is now d 2 C. m 2 (e80Ci) 100, 7 T0,
p S min exxp(d/(EC)) In (m ((80C:) 1 20:0g7
d'In(m 0.01 /8UCI) f S exp (exp (d/C)/8) and p pln(t)= I 8CC
Thus, with the universal constant C' = max (E80Ci) 100 AC,, C] and m, m. 2 C and S 1/C we have that the expected loss is at least m 0.01 when p < min (cxp(O 0(n (m)//7}}
t S exp (exp (O(d)) and pudppll pln(t) S O(d In (m)/>²) which concludes the proof.
We now move on to prove Theorem C.2. For this, we now introduce what will call the extension of A which still terminates if it receives a hypothesis with loss more than 1/2 -y. We further show two results about this extension one which says that with high probability we can replace A with
its extension and another saying that with high probability the loss of the extension is large, which combined will give us Theorem C.2.
The output of the extension B of A on input (S, c(S), W) is given through the outcome of recursive query sets Q!..... where each of the sets contains queries. The recursion is given in the following way: Make Q² to W as A would have done on input (S, (S,c()),)) (this is possible by Assumption C.1 which say Q' is a function of only (S)c()))). For
1, .,....7 ......PP...................... such that for all j ,,, it is the case that W(Q)-1) has loss less than 1/2 7 under Dj- let Q' be the query set Q that A would have made after having made query sets Q'...... " Qii- and received hypothesis (V()))aannett (xx If this loop ends output the hypothesis that A would have made with responses [W()))...ee
its queries. If there is an L such that W(Q)) return hypothesis with loss larger than 1/2 - y return the all 1 hypothesis.
We now go to the two results we need in the proof of Theorem C.2. The first result Corollary says that there exists an event E which happens with high probability over H.p..RR R such that A run with This corollary can be proved by following
WHHp.e, R, c) is the same as B run with W(H, the proofs of Theorem 5 and 8 in Lyu et al. [2024] and is thus not included here.
Corollary 1. For d N. m E N. margin <<<= < 1.
ach. labelling function c [2m] - 1-1,
p.p.t E N. random matrix H.p...R. learning algorithm A, BA, training sample S E [2m]'", we have that there exist and event E over outcomes of p. such that
A(S,c(8), W(H n Uc)) = BA(8,c(S), -. W(H,..,)))
and
Pr [ 2 pl exp (-Rd).
H pp...
The second result that we are going to need Lemma C.3 which relates parameters R, 3, p to the success of any function of (S, c(S), Hp...n) which tries to guess the signs of c which is the number of failures in our hard instance. For a training sample S E [2m]* we will use [S] to denote the number of distinct elements in S from [2m], for S [2m]" we have |S| < m
21

---

Lemma C.3. There exists universal constant C.. Ct 2 such that: For m E N. p.p.C. P N, H.B. function B that takes as input S [2m]] with labels c(S), and hypothesis R.B.ReRR have that
(2m |S]] exp((CiC3))
Pr C.Hb.e,R
Σ 1(B(S,c(S) H (t) c
2C:
(2m (2m-15) (2m-15)eep(CCCCC7711)
exp
8C₁
We postpone the proof of Lemma C.3 and now give the proof of Theorem C.2.
Proof of Theorem C.2. We want lower bound Es.e, es.e.Hlll ( W(H Uc))]. To this end since S and are independent and Hp...n depended on the expected loss can be written as
W(HUe)))]
E (A(S, c(S), W(Hp,..R Uc))]]
Es Re Hp... (A(S, c(S), W(Hp.., Uc))]]]]-
Now let S E [2m]] be any outcome of S and c. Then for these S, we have by Lemma C.3 that there exists some event E over H. such that
()(A) R.R.R. c))) (B W(Pp..
and
Pr H.p.c.R
[ pt exp (-Rd),
furthermore, define E' be the event that
2m
c(i) (2m - (Sm) exp( exp(-
Ex
I(BA(S, ((H
2C:
Using the above and U being the uniform measure [2m] assigns 1/(2m) mass to every point and that |.S] S m we now get that Expp.. (A(S, W R. e)))] 2 Exp.... ((S),, W(H R. (.),,,c)))ll11p
E.n...K (BA c(S), W p.c. )
1
1
(2m |S|) exp(((((
E EzH, [ [gl
40mm
exp( exp(-CiC37²RP) (1-
Pr Hp.e.
E pt e Rid
4C₁
We can do this for any pair and S E [2m] m, so we have that
Eg [E o. (A(S, W(( R Uc)))]]
expl CG
(1
Pr
E
pt exp Rd)
4C1
c. H.P.RRRR
Now by Lemma C.3 and
|S]
S m we have that PIe
Hy H.R.R
at most
(2m (S])
mexpp mexp(-CCCC
Pr E' S exp HyH.e.R
< exp
8C₁
8C₁
Le. we have shown that
Ee (
W(H p. Uc])]]]
exp(- 2xp(-C9Ch220) Rp) ( exp
m mmmxppppCCC Rp)
exp
(
exp (- RRd)
4G,
8C1
for any SE [2m]m m. Now by taking expectation over S ~ Lm we get that
Es.c (C c(S), W(H, Uc))]]
exp( (CCCC Rp) (1 (1-esp
mexp( 2
pt exp -peepp (-Rd)
4C₁
8C₁
which concludes the proof.
22

---

We now prove Lemma C.3 which is consequence of maximum lii-i-iiiliiodd, and the following Fact I, where Fact gives lower bound on how well one from n trials of a biased {-1, 1) random variable, where the direction of the bias itself is random, can guess this random direction of the bias.
Fact For function f 1-1,1 + (-1,1} and 0 < S ac.
ce 1,1) ( [Lf((b) + ctll exp(- exp(-CCC3,Pm)/C
Proof. This is the classic coin problem. The lower bound follows by first observing, by maximum- likelihood, that the function f' minimizing the above error is the majority function. The result then follows by tightness of the Chernoff bound up to constant factors in the exponent.
With Fact in place we are now ready to proof Lemma C.3, which we restate before the proof
Proof of Lemma C.3. Let Hc, be the matrix consisting of the i.i.d C&y biased matrices in Hpp..R.
He" ...., HeP stack top of each other,
H
HCc. :
H
Furthermore, for = I,..., 2m let H.c., denote the ith column of He, which is vector of length pR. Now for inside S, B has the sign of c(i), so the best function that B can be to be equal to c(t). For i outside S, B does not know c(2) from the input but has information about it through H.c..s. we notice that the sign's of the hypotheses in H H..... H- and Hoss j * and c(S) is independent of e(i) and does not hold information about c(t). thus the best possible answer any can make is to choose the sign which is the majority of the sign't 's in Ho, the maximum likelihood estimator. We now assume that
this -eove-deeridbed "best" function as this function will be lower bound for the probability of failures for any other B, so it suffices to show the lower bound this B. Now with the above described B, we have that
pR Σ
X Σ 1(B(S,c(S), Hpp.c, c(1) I
Honss
* c(t)).
EES
Thus, we have that X is sum of 2m |S| (where |S] is the number of distinct elements in S) independent {0, 1] -randdo variables and by Fact 1 we have that the expectation of each these ran- Rp)/Ct. Thus, now get by
dom variables is at least Ee,Hp,.. [X] 2 (2m - exp) Chernoff that
(2m ((]) 3xxpp-C,772BRp
Pr e.H.p.OR
X>
Pr [ > [[X
2C₁
c.
C.H.p.OR
expeepp (-[(x/88 1-exp (- (_(2m (2m
151) C
8C₁
as claimed.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical claims in the introduction and abstract exactly match what prove in the paper and claim as the scope and contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [NA]
The paper is theoretical, so given the assumptions of the claims, there are no limitations.
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
24

---

Answer: [Yes]
Justification: The main paper includes a proof sketch for both the upper and lower bound. Parts of the formal proofs of the upper bound and lower bound are in the main text and the remaining are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relics upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: The paper is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
The paper is theoretical, and we have no experiments, data or code in the paper.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines battps://nips..e cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips.... ccccccpppa.o htc/public/aae hg/gguidee/////// Sedeeeeeeooeeebbiiiie ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: The paper is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
The paper theoretical, and we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative еπτог rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
The paper is theoretical, and we have no experiments, data or code in the paper.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics attps:// //teur:p//nurips.... ctlpp.ccc/ppppeee http/puli//ttiissuuuie
Answer:
[Ye]]
Justification:
We no violations of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The result of the paper is theoretica//foundatinnal research, so we have no experiments, data or code in the paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
27

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
The paper is theoretical, and we have no experiments, data or code in the рaper.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
The paper is theoretical, and we have no experiments, data or code in the paper.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
28

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper is theoretical, and we have experiments, data code in the paper.
Guidelines:
The answer means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given to participants and screenshots, applicable, well as details about compensation (if any)?
Question:
Answer: [NA]
Justification: The paper is theoretical, and we have experiments, data code in the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is theoretical, and we have no experiments, data or code in the paper.
Guidelines:
29

---

The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "VVgknXohbg", "reviewer": "Reviewer_D6oP", "summary": "The authors offer the  bound of algorithm 1 in  paper in a very traditional learning theory.", "questions": "Please show the importance of algorithm 1 or show that algorithm 1 can accelerate model training under the same computing resource.", "limitations": "The same with weakness", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I think a theory understanding of the algorithm is more important than the experiment reports. This paper shows the bounds for a kind of parallel boosting algorithm. The proof sturcture of algorithms is clear. Authors present their work clearly.", "weaknesses": "The most important problem for this work is the view of boosting and the applicability of algorithm 1.\n1. After the work of XGBoost, the proof of boosting is to minimize the loss value of model on training dataset instead of the combining the weak learners. From this aspect, can we gain a better bound or design a better parallel boosting algorithm?\n2. I really like the proof work in this paper, but the  fatal problem in this paper is that the algorithm 1 may be not accelerate the model training. For line 10 to line 18, the algorithm have to find $h^*$ in $H_{kR+r}$ and this process may be a exhausting work, which means algorithm may cost more time than traditional boosting with the same computing resource.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the effort invested in evaluating our submission. We were happy to see that the reviewer found the presentation of our arguments clear and values the theoretical nature of our work, which is its entire focus.\n\nWe remark that with a lot of parallel computation, the time to find $h^\\star$ in $H_{kR+r}$ may be reduced (that is, the time to completion, not the total work). In particular, one thread can evaluate the performance of each $h \\in H_{kR+r}$ in parallel and then the best performing $h^\\star$ can be computed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tNWf0HrHM0", "reviewer": "Reviewer_umpM", "summary": "The authors study parallelized boosting, a natural weak-to-strong learning model recently re-introduced by Larsen and Karbasi. Building on recent work of Lyu et al., this work gives new upper and lower bounds on the trade-off between number of rounds, and number of parallel calls per round to the weak learner, and in particular resolves the complexity of parallel boosting up to log factors in a certain natural parameter regime.\n\nA boosting algorithm is a method for amplifying a `weak’ learner assumed to have some advantage $\\gamma$ (that is classification accuracy $1/2+\\gamma$) to a strong learner (achieving accuracy $1-\\varepsilon$ with probability $1-\\delta$) by repeated rounds of calls to the weak learner on sequentially modified ground distributions, typically taking a weighted majority vote of the results.\n\nA $(p,t)$-parallelized boosting algorithm makes p rounds of t-calls to the weak learner, where each round can only depend on the outputs of previous rounds. The authors main result is a new upper giving a tradeoff between $p$ and $t$ for learning any hypothesis class $H$ with VC dimension $d$. In particular, for any $R \\in \\mathbb{N}$, they give a boosting algorithm with\n\n$$p=\\frac{\\log(m)}{\\gamma^2 R}, t=e^{dR}\\log\\frac{\\log m}{\\delta R}$$\n\nHere $m$ is the number of samples used by the algorithm, which is assumed to achieve near-optimal accuracy-sample trade-off $m \\approx \\tilde{O}(d\\varepsilon^{-1}\\gamma^{-2})$. This improves over prior work which gave a similar result for $t=e^{dR^2}$, reducing the R-dependence from quadratic to linear in the exponent.\n\nSecond, the authors improve prior lower bounds on parallelized boosting to show their bound is near-tight in many regimes of interest. In particular, they prove that either $p \\geq \\min(exp(d), \\log(m)\\gamma^{-2}))$ or $t \\geq exp(exp(d))$, or $p\\log t \\geq d\\gamma^{-2}\\log(m)$. The last of these matches the upper bound up to log factors, so the authors resolve the problem in the regime where $t < exp(exp(d))$, $p < \\min(exp(d), \\log(m)\\gamma^{-2})$, and under the requirement of near-optimal accuracy-sample tradeoff.", "questions": "It Is it possible one might achieve better trade-offs by relaxing the sample-optimality assumption? Or is this largely an assumption made to simplify the formulae for $p$ and $t$ in terms of samples and not accuracy.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Boosting is one of the most successful and broadly used paradigms in machine learning. Understanding the extent to which boosting can be parallelized is a core problem, and of great interest to the learning theory and machine learning communities. This work makes substantial progress on resolving the complexity of parallelized boosting.\n\nThe main technique introduced to improve Lyu et al.’s upper bound is a novel and elegant \"win-win\" theorem, analogs of which may be useful in other problems. The rough idea is to \"simulate\" sequential boosting distributions $D_0,\\ldots,D_R$ in each round, and look at $KL(D_0,D_R)$. If the KL between these distributions is close, the authors argue that one can essentially simulate sampling from $D_R$ by sampling from $D_0$ (up to some small error), meaning the `simulated’ boosting will be successful and adopt the guarantees of standard sequential boosting. If the KL is large, we cannot simulate samples but this indicates the boosting algorithm has made progress and we win anyway. This method removes the sub-optimal $R$ factor from Lyu et al.’s method using the simpler max-divergence instead of KL-divergence.", "weaknesses": "My main complaint is that I feel the results are a little bit over-stated in the abstract and early in the introduction, which claims to essentially resolve the complexity of parallelized boosting. This doesn’t really seem true, since as discussed above the problem only seems to be resolved (up to log factors) under three assumptions:\n\n1.   $t < exp(exp(d))$\n\n2.   $p < \\min \\{exp(d), \\log(m)\\gamma^{-2})\\}$\n\n3.   The algorithm is required to have near-optimal accuracy-sample tradeoff.\n\nNote that the latter $p$-dependence is not so restrictive, since this is achieved by non-parallel boosting (I.e. t=1), but the other parameter regimes remain open. It is unclear to me how restrictive the last condition is. It seems very reasonable one would be willing to sacrifice somewhat on samples to achieve higher parallelization; is this possible?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. As for Reviewer GD3o, we see that the present reviewer got a solid understanding of our work and its contributions. The question posed by the reviewer attests to this and, once again, we share our opinion that such level of comprehension is suitable for a higher confidence score.\n\nAnswering the question, it is indeed possible to achieve better $p$ vs. $t$ tradeoffs by further relaxing the restriction on the sample complexity of the algorithm. In more detail, the $\\log n$ factor in the upper and lower bounds may be replaced by $\\log(1/\\varepsilon)$ factors for a target accuracy of $\\varepsilon$ greater than or equal to the accuracy we obtain. We chose to focus on the near-optimal accuracy regime to keep the formulas as simple as possible with the already numerous parameters.\n\nWe agree with the author that emphasizing it can make the scope of our contribution clearer. We will add a discussion of this to the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DzIT2d254v", "reviewer": "Reviewer_GD3o", "summary": "This paper studies parallelization in weak-to-strong boosting algorithms. Such algorithms are modeled by the number of sequential rounds $p$ that they run for, and the amount of work $t$ that can be done in parallel in each round. Each unit of work in a round is typically a query to a weak learning algorithm, that outputs a hypothesis from a class of VC dimension $d$ (and these queries can be instantiated in parallel). Formally, in round $i$, the algorithm invokes (in parallel) the weak learner with distributions $D^i_1,\\dots,D^i_t$, and obtains $h^i_1,\\dots,h^i_t$ such that the error of $h^i_j$ wrt $D^i_j$ is at most $1/2-\\gamma$. There are $p$ such rounds, at the end of which, the weak-to-strong learning algorithm outputs some weighted vote over all the $h^i_j$s obtained so far. Ideally, we want the final classifier output by the algorithm to be *strong*: at the very least, its error should be competitive with that of AdaBoost (which is $\\tilde{O}(d/m\\gamma^2)$ where $m$ is the number of training samples).\n\nUnder a model of weak-to-strong learning defined as above, the classic AdaBoost works with $p=O(\\ln m / \\gamma^2)$, and $t=1$. What are some other reasonable tradeoffs that we can hope for?\n\nKarbasi and Larsen (2024) gave an algorithm that works with $p=1$ and $t=\\exp(O(d \\ln m / \\gamma^2))$. This was followed up on by Lyu et al. (2024), who obtain $p=O(\\ln m/\\gamma^2R)$ and $t=\\exp(O(dR^2))\\ln(1/\\gamma)$ for any $1 \\le R \\le 1/2\\gamma$. Both Karbasi and Larsen (2024) as well as Lyu et al. (2024) also gave some lower bounds, but neither covered the entire spectrum of $p$ and $t$ in terms of tightness with respect to algorithms achieving these bounds.\n\nThis paper largely fills up these gaps. On the upper bound side, the authors present an algorithm that achieves $p=O(\\ln m/\\gamma^2R)$ and $t=\\exp(O(dR)) \\ln \\frac{\\ln m}{\\delta \\gamma^2}$ for any $R \\ge 1$. Observe that the bound on $t$ improves Lyu et al. (2024)'s bound by a factor $R$ in the exponent. The authors also show lower bounds that are tight (upto log factors) in nearly in all regimes.\n\nBoth, the algorithm for the upper bound, and the lower bound instance, are inspired by the work of Lyu et al. (2024). \n\n### **Upper bound**\n\nThere are $p$ sequential rounds. For simplicity, we describe the first round, prior to which $D_1$ is set to the uniform distribution on the training sample. We break our computation into $R$ chunks in parallel. Each chunk, invokes a weak learner $t/R$ times in parallel on a fresh sample drawn from $D_{1}$, to obtain $t/R$ many hypotheses in total (Thus, the total number of invokations to the weak learner across all the $R$ chunks is $R \\cdot t/R = t$ as required.) \n\nThereafter, there are $R$ sequential rounds of boosting. As $r$ ranges from $1,\\dots,R$, we try to obtain a classifier that has error at most $1/2-\\gamma$ with respect to $D_r$. We simply do this by checking if there was a hypothesis in the $r$th chunk that has such an error with respect to $D_r$ using the sample we had (which, notably, was from $D_1$). If we do find such a hypothesis, we do a standard boosting update to derive $D_{r+1}$. Assuming that the hypotheses in each step had the required errors with respect to $D_r$, we can imagine that each step works correctly as a standard boosting step, and hence, in each of the $p$ rounds, we are in fact doing $R$ rounds of boosting (and hence, $p$ can be a factor $R$ smaller than standard AdaBoost).\n\n\nBut do the hypotheses in each step have the required properties? When we have a sample from $D_1$, we can simply see if a hypothesis has error at most $1/2-\\gamma$ with respect to $D_1$ by checking the error of the hypothesis on the sample itself --- this follows from standard uniform convergence of VC classes. However, what if we have a sample from $D_1$, but want to check if a hypothesis has error at most $1/2-\\gamma$ with respect to $D_2$? Can we still use the empirical error on the sample as a proxy? In fact, this is what the algorithm is doing in each boosting step. Intuitively, if the distributions $D_2$ and $D_1$ are \"close\", this should still work. But note that we make exponential updates to $D_1$ in the boosting step, so it is not obvious at all that $D_2$ should be close to $D_1$. Lyu et al. (2024) control the max-divergence between $D_2$ and $D_1$, and show that this recipe works by using sophisticated tools like advanced composition from differential privacy. This is where the authors diverge (no pun intended): instead of the max-divergence, the authors control the KL divergence between $D_2$ and $D_1$ instead. This is acheieved by using the Gibbs variational principle. The technical analysis seems highly non-trivial, but gets the job done: with good chance over the sample, the empirical error on a sample from $D_1$ is going to be a good proxy for the distributional error on $D_2$, provided the KL divergence between $D_2$ and $D_1$ is small. If the KL is not small, then the authors show that progress has already been made. In this way, by tracking KL divergence instead of the max-divergence, the authors are able to improve over the bound of Lyu et al. (2024).\n\n### **Lower bound**\n\nThe analysis for deriving the improved lower bound is much more involved. We first start by describing the high level construction in Lyu et al. (2024). The ground truth hypothesis is a random concept $c$ on a domain twice the size of the training set. The hypothesis class $\\mathcal{H}$ that the weak learner operates over is also constructed randomly. In particular, it contains $c$, and also $p$ other hypothesis $h_1,\\dots,h_p$, where each $h_i$ on each $x$ agrees with $c$ with probability $1/2+2\\gamma$. The VC dimension of this class can be controlled in terms of $p$. Now, whenever the weak learner gets queried with a distribution $D$, if it can satisfy this query by returning a hypothesis that is not $c$, it does so. The goal is to argue that the weak learner can get away with never having to return $c$ at all in any round. If this is the case, what the learning algorithm knows about the rest of the domain is only in the form of $2\\gamma$-biased coins. By instantiating the lower bound on learning the bias of a coin, we get a lower bound on the number of rounds.\n\nLyu et al. (2024) require the number of queries $t$ in each round to be sufficiently small for the weak learner to never return $c$. The main observation by the authors is that, indeed, it is possible to use a much bigger bias than $2\\gamma$ in the construction of $h_i,\\dots,h_p$. That is, each hypothesis can be biased towards $c$ to a much larger extent (as much as $\\sqrt{\\ln(m)/p} \\gg 2\\gamma$). This lets them relax the number of allowed queries $t$ per round, which ultimately yields the stronger lower bound.", "questions": "Is there some intuitive meaning to the lower bound of $t \\ge \\exp(\\exp(d))$, even at a very high level? It seems like such a bound on $t$ (albeit weaker) also existed in Lyu et al. (2024). Do you have any thoughts on how one may attempt to close it, or the inherent difficulty?", "limitations": "The authors adequately address any limitations that I can foresee.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This paper essentially completes the characterization of the tradeoff between the number of sequential rounds and the parallel work in each round in boosting algorithms. Previous work left gaps between the upper and lower bounds across much of the spectrum of these parameters. The authors improve upon the state of the art, using highly non-trivial analyis tools, and essentially close the gaps across nearly all of the spectrum. We now have a significantly more complete picture about the tradeoffs involved in parallelizing boosting thanks to the authors' work.", "weaknesses": "The paper \"Boosting, Voting Classifiers and Randomized Sample Compression Schemes\" (https://arxiv.org/pdf/2402.02976) by da Cunha et al. (2024) is a relevant paper to the present work---in particular, we can get rid of at least one of the two log factors in the error of AdaBoost with a voting classifier. I recommend the authors at least mention this and cite the paper.\n\nI would also encourage the authors to discuss (somewhere in the paper, maybe as a separate paragraph, or in the conlusion) a bit more about the only regime that we still don't know a matching upper bound for: that of $t \\ge \\exp(\\exp(d))$. \n\nMinor/typos:\\\nLine 64: $n$ hasn't been introduced yet (it should be the size of the training set? and maybe also use $m$ then?)\\\nLine 132: Shellah -> Shelah", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful evaluation of our work. It was a joy for us to read it. It is clear that the reviewer built a solid understanding of our work, grasping multiple of the subtleties in the argument. This even extends to related works to some extents, as evidenced by the reviewer's comments and the insightful suggestion of a recent reference, which we will adopt. In fact, in our opinion, such level of comprehension seems deserving of a higher confidence score.\n\nRegarding the question on why the $\\exp(\\exp(d))$ term appears, indeed it is somewhat unclear whether it should truly be there. Simply examining the calculations, it originates from the following argument in the lower bound: For each parallel round, we have around $N=\\exp(d)$ many random hypotheses that could be used to answer the query distributions (since the VC-dimension is $d$). Since the query distributions in round $i$ are independent of the random hypotheses used to answer queries in round $i$, if each of them is a valid response with just constant probability (say $1/e$), then the chance that none of them are a valid response to a fixed query distribution is only $e^{-N} = \\exp(-\\exp(d))$ (recall the hypotheses are chosen randomly). So for a parallel algorithm to ask a query that forces the weak learner to return the true concept, we would need to ask around $t = \\exp(\\exp(d))$ queries. We acknowledge that this is not super intuitive, but at least this is where it originates. It would be very interesting to exploit this in a new algorithm.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The reviewers unanimously agreed that this is a theoretically solid paper that contributes several strong upper and lower bounds for understanding parallel boosting algorithms. The meta-reviewer would be happy to recommend the paper for acceptance.
Decision: Accept (oral)