Sample-Optimal Agnostic Boosting with Unlabeled Data

We thank the reviewer for their comments.

Runtime overhead over PAB: We remark that both in theory and in practice, our algorithm is no slower than the PAB algorithm of Kanade et al. To achieve $\varepsilon$-excess error, the PAB algorithm performs $1/\gamma^2 \varepsilon^2$ rounds of boosting in each of which the weak learner is fed $VC(\mathcal{B})/\gamma^2 \varepsilon^2$ samples; the same is true for us (see the setting of parameters in the theorem statement). In terms of implementation, the PAB algorithm samples $VC(\mathcal{B})/\gamma^2 \varepsilon^2$ samples fresh from the population distribution; we sample half this number from a pool of previously sampled labeled data points, and the other half from freshly sampled unlabeled data points. Therefore, the running times of PAB and Algorithm 1 are remarkably similar.

Novelty of results and techniques: While our proof techniques build upon prior work (and the exposition is carried out so that this is as clear as possible, and so that our changes are conspicuous), we believe our contribution goes beyond incremental improvements. The conception that unlabeled data can specifically ameliorate the sample complexity gap in agnostic boosting is novel and opens new directions for semi-supervised boosting research. This connection wasn't previously recognized despite its simplicity in hindsight.

Next, we come to techniques: Despite employing a variety of other techniques, agnostic boosting algorithms (e.g., Kanade et al, Ghai et al) almost invariably use the Madaboost potential (Domingo et al), and in fact so do hundreds of other robust boosting algorithms. Our key innovation is orthogonal to other existing algorithmic techniques, which is why it can be layered on top of Kanade et al and Ghai et al. We introduce a new potential function, crucially which via linearity of expectation, can be written so that it decomposes into two parts, one estimable based on labeled data, and the other based on unlabeled data. Furthermore, it is essential the first labeled data part (formally, its derivative) does not depend on the ensemble whose value is being assessed; this allows us to reuse the same set of labeled data across all rounds of boosting (unlike Kanade et al) without needing a uniform convergence argument (as in BCHM) or a martingale argument (in Ghai et al).

This new potential function violates some key tenets of prior work. For example, the centerpiece of the Madaboost potential is that it (formally, its functional derivative) does not downweight points that are misclassified by the ensemble. This property is best captured in the definition of a conservative relabeling in Kanade et al. Intuitively, it makes sense; one wants not to withdraw any focus from wrongly classified data points. Not only is this false for us, it is incompatible with the requirement of having a separable potential function, which we have just described. This can be seen in Figure 1– the derivative of Madaboost for negative domain is always -1, but for us this is not true, and our potential curves upward between [-1, 0]. Here, our proof technique, despite seeming syntactic similarity, has been modified to handle this.

Finally, it is worth pointing out that the setting of covariate shift requires a number of changes to keep track of the progress being made in each round of boosting. Foremost among these is the potential function, which is no longer the population (expectation) version of a scalar potential. We keep track of the progress on the labeled and unlabeled distributions separately.

Range of experiments: The primary contribution of our work is theoretical, as Reviewer P5aa also notes. Our main innovation is the design of a potential function whose use in the potential based boosting framework permits the use of unlabeled samples to make learning more sample-efficient. Since this is an improvement that can be composed with other innovations, like the sample reuse scheme in Ghai et al, our experiment setup thus is an ablation study meant to verify the hypothesis that additional unlabeled samples can enhance the learning performance in agnostic boosting. And in it, Algorithm 1 which is a close modification of PAB from Kanade et al is compared to PAB. We strongly feel such ablation studies which measure the improvement induced by individual algorithmic techniques is the right way to make and measure progress on foundational problems, as opposed to a leaderboard approach. Finally, we remark that our datasets are of comparable sizes to ones considered in Kanade et al.

Intuition: We hope that our self contained 1.5 page proof can aid future readers. But crudely, the potential is such that for unlabeled data, the relabel distribution shifts towards negative examples when $H_t(x)$ is positive and positive examples when $H_t(x)$ is negative. This acts as a regularizer against high certainty predictions on data without labels.

We thank the reviewer for their comments.

Statistical Gains over Realizable-Agnostic Reduction: At the outset, we find this to be a loaded question (i.e., one that in our view has an unfair presupposition built in). If one were to discard computational constraints, one can perform ERM on the target class with $VC(\mathcal{H})/\varepsilon^2$ samples, and achieve an optimal sample complexity. This, via classical VC results, is unimprovable; for each $\mathcal{H}$, there’s a distribution for which this is tight. The reduction outlined by the reviewer – which we are certainly happy to cite and highlight – also gets $\propto 1/\varepsilon^2$ sample complexity. Getting the class-specific dependencies right via this approach takes additional work and has been pursued in a recent preprint that we have been recently made aware of (which we can not link here because they cite our work). However, note that this reduction requires pruning the hypothesis class by enumeration while considering all possible labellings of $VC(\mathcal{H})/\varepsilon^2$ samples, and hence takes exponential time.

Over such computationally inefficient, and in the case of ERM, also statistically optimal, exponential time approaches, we offer no statistical improvements. But here we remark that neither does the celebrated Adaboost algorithm. Boosting is a question that arose in computational learning theory (i.e., in Valiant-lore as opposed to statistical learning aka Vapnik-land), and its primary purpose has since its origin been and continues to be computationally efficient reductions, which we also pursue. Like all known boosting results, and unlike exponential time approaches, our results make a polynomial number of calls to the weak learning oracle – in fact we are no worse than any other agnostic booster in this regard quantitatively – and perform polynomial work. Now it is natural to ask if these computational benefits come at a statistical cost, and this is the question we make progress on.

To summarize, the purpose of our work is to give computationally efficient boosting algorithms that are yet better than known ones in terms of sample requirements. It is thus unsurprising that we are no better statistically than exponential time approaches (such as ERM or exponential time agnostic-realizable reductions).

Novelty: Our intention was always to say that the consideration of unlabeled samples is new in the agnostic boosting context. Indeed outside it, there’s a massive body of work on semi-supervised learning. Here, we also thank the reviewer. The works of Hopkin et al and David et al are definitely worth pointing out in the broader statistical learning context; we will add a discussion on this line of work. However, both our context and our techniques owing to mandates of computational efficiency are disjoint from Hopkins et al, to the best of our reading. Unlike Hopkins et al, we do not coarsen the hypothesis space by considering all possible labellings of some set of points. Our intuition and proof is based on synthesizing a potential function in the framework of Kanade et al, whose parts can be independently estimated on labeled and unlabeled data, respectively.

In light of this clarification regarding the positioning of our paper (and of boosting broadly), we would like to gently petition the reviewer to consider raising their score.

PS. This is a minor point in the grand scheme of things. But the realizable-boosting reduction, to the best of our reading, would also break the distribution-specific nature of the weak learners (discussed on page 3), since Adaboost does not preserve the marginal distribution over features.

We thank the reviewer for their thoughtful comments and thorough review. We will execute all the suggested editorial suggestions upon revision.

Experimental setup: Each dataset is split into a labeled sample pool and an unlabeled sample pool; the labels for the unlabeled sample pool are discarded. The precise ratio of this split is given in the footnote on page 8. The contract in our comparison is that Algorithm 1 and PAB across the course of entire execution have access to the same pool of labeled samples. Algorithm 1 additionally can access the unlabeled pool. Our experimental setup thus is an ablation study meant to verify the hypothesis that additional unlabeled samples can enhance the learning performance in agnostic boosting. The ability to achieve lower error when given access to the same pool of labeled samples indicates that the learning is now more label-sample-efficient.

Through its execution PAB, the algorithm from Kanade et al, has access to only the labeled pool. PAB is an iterative boosting algorithm that does not reuse samples between its rounds. Hence, the number of samples available in each round of boosting in PAB is the number of labeled samples / number of rounds of iterations. In contrast, following the description in Algorithm 1, our algorithm via subsampling can reuse the same set of labeled samples across multiple rounds, although unlabeled samples used every round must be fresh.

We thank the reviewer for their thorough review. Both the suggestions – introducing $\gamma$ early and defining the VC dimension – are well noted, and we will execute these upon revision.