Optimal Parallelization of Boosting

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).

Under 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?

Karbasi 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.

This 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.

Both, the algorithm for the upper bound, and the lower bound instance, are inspired by the work of Lyu et al. (2024).

Upper bound

There 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.)

Thereafter, 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).

But 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).

Lower bound

The 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.

Lyu 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.

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.

A 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.

A $(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

$p=\frac{\log(m)}{\gamma^2 R}, t=e^{dR}\log\frac{\log m}{\delta R}$

Here $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.

Second, 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.

The authors offer the bound of algorithm 1 in paper in a very traditional learning theory.

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.