Subsampled Ensemble Can Improve Generalization Tail Exponentially

Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.

Q3: The proposed method envisions always using one single learner (extracted through majority voting or finding the eps-optimal one), and justifies how this improves generalisation. Intuitively, often using boosting/bagging is a much more powerful solution (e.g. boosted ensembles such as XGB perform way better than single decision trees). Indeed in Figure 2 you show that for light-tailed distributions subagging wins over ROVE. (1) Is this always the case? Does your method always wins for heavy-tailed distributions? (2) Were you able to find a "cutoff" which tells when your method is preferable, depending on how data is distributed? Can you extract this somehow from the training data? (3) Have you compared your algorithms to other ensembling techniques other than bagging (from Figure 2)?

A: Thank you for the questions. The goal of our work is to provide a fresh perspective, especially for problems that suffer from heavy-tailed noises, that by performing voting (subsampled ensemble) on the model level instead of the output level, one might be able to achieve better generalization performance. Although the output model from our algorithms is one of the base learners, the main message we want to convey is not that "a single tree can do better than an ensemble of trees". Instead, we want to demonstrate that by carefully selecting a model from the candidate sets, one can possibly achieve the generalization performance that a simple aggregation cannot offer (for example, for heavy-tailed problems, a simple average might not effectively reduce the noises).

In theory, as long as the mild assumptions stated in our theorems are satisfied, our methods are guaranteed to have the exponentially decreasing excess risk tails. This is what other ensemble approaches do not have. Indeed, in our new experiments shown below, our methods outperform all popular ensemble methods in tail performance when the problem gets heavy-tailed.

W2: Comparison with tree ensembles

A: We have added a new set of experiments comparing our approach with popular existing tree ensembles, including Random Forest (RF), Gradient Boosted Decision Trees (GBDT), and XGBoost (XGB). Decision trees are used as the base learner for all methods. Random forests are constructed with the same number of decision trees as our methods to ensure a fair comparison. GBDT and XGB are constructed with early stopping to avoid overfitting. Results on percentiles of the test errors are as follows:

Comparison with tree ensembles in terms of tail performance

For the same synthetic data as described in lines 209-212

• $n=2^{11}$, Pareto shape = $1.5$

• $n=2^{11}$, Pareto shape = $2.0$

• $n=2^{11}$, Pareto shape = $2.5$

For a new synthetic data $Y=10\sum_{i=0}^{9}2^{-i}\sin(2\pi X_i)+\epsilon_1-\epsilon_2$ where each $X_i$ is uniform on $[0,2]$ and $\epsilon_1,\epsilon_2$ are Pareto

• $n=2^{15}$, Pareto shape = $1.5$

• $n=2^{15}$, Pareto shape = $2.0$

For a new synthetic data $Y=10\sin(2\pi X)+\epsilon_1-\epsilon_2$ where each $X$ is uniform on $[0,2]$ and $\epsilon_1,\epsilon_2$ are Pareto

• $n=2^{15}$, Pareto shape = $1.5$

• $n=2^{15}$, Pareto shape = $2.0$

These results show that our methods outperform the base learner in almost all cases, and also outperforms RF, GBDT, and XGB especially in high percentiles when the tail is heavy (e.g., with Pareto shape 1.5). For not so heavy-tailed cases RF, GBDT, XGB may outperform our methods.

Q1: I'm not entirely sure I get the discrete scenario. The majority vote in MoVE happens over the different trained models. Does that mean multiple models that are exactly the same are the output of the training on different subsamples? e.g., we would need to have two identical decision trees? Or is this for example related to the numerical solution of a stochastic program? Could you please provide a practical example of a discrete scenario? It's probably just a lack of expertise on my side.

A: We are certainly happy to provide more clarifications. A discrete scenario refers to problems where the decision space consists of discrete solutions. In such cases, when solving the same problem on multiple subsamples, some solutions may appear repeatedly across different base learners. In the machine learning context, a good example is model selection where one selects a final model among finitely many candidates. It indeed more naturally arises in stochastic programming with discrete solution space.

Q2: In addition to the formula in the algorithm, could you better explain in a couple of sentences and/or with an example what it means that a model is eps-optimal?

A: No problem! In general, a solution $\theta$ is called $\epsilon$-optimal for the optimization problem $\min_{\theta\in\Theta} L(\theta)$ if its loss satisfies $L(\theta) \leq L(\theta^\star) + \epsilon$, where $\theta^\star$ is the true optimal solution.

In the specific context of Algorithm 2 (ROVE/ROVEs), a solution $\theta$ is considered $\epsilon$-optimal on a given subsample if, when evaluted on that subsample, its loss is within $\epsilon$ of the best loss achieved on that subsample. For each subsample, Phase II of Algorithm 2 basically finds all such $\epsilon$-optimal solutions among the retrieved solutions. Finally, the algorithm selects the solution that is $\epsilon$-optimal for the largest number of subsamples. This procedure can be viewed as a generalized majority vote in the continuous space.

W1: Hard to verify the condition $\eta_{k, \delta}>0$ for a given algorithm $\mathcal{A}$ and a given $\delta>0$.

A: Although it can be nontrivial to verify the condition since it's not as explicit as moment or structural conditions, we choose not to use more explicit conditions in order to make the theorem lightweight and at the same time convey enough insight regarding the behavior of the algorithm. In particular, the theorem clearly shows the difference our algorithm makes --- our explicit bound (10) clearly demonstrates how the tail $\mathcal{E}_{k,\delta}$ of the base learner is improved by the ensemble. We figure that this forms a good balance between technical complexity and the insightfulness of the theorem.

W2: Restrictiveness of the condition $\eta_{k, \delta}>0$

A: Thanks for pointing out this. This condition can be relaxed. We use this more restrictive condition in Theorem 2.1 to streamline the presentation. See Theorem C.8 for the original version of this condition in equation (28), where we compare the global mode of the solution space with the mode among all non-$\delta$-optimal solution. We can readily replace the condition in Theorem 2.1 with this relaxed condition without affecting its validity. This relaxed condition can be satisfied by the example provided by the reviewer.

W4: Comparing tail probability with bagging

Percentiles of test performance

• $n=2^{13}$, Pareto shape = $1.1$

• $n=2^{13}$, Pareto shape = $1.5$

Q1: If $\eta_{k, \delta} \leq 0$, what can be said?

A: We do not have a bound for tail in this case.

Q5: In Algorithm 2, can you speficy "Choose $\epsilon \geq 0$ using the data..."? How is $\epsilon$ picked practically such that it satisfies the conditions in Theorem C. 11 , which seem hard to check?

A: Thank you for the question. It is nontrivial to pick $\epsilon$ to satisfy the technical condition in Theorem C.11. In practice we use an adaptive strategy for choosing $\epsilon$. Yet, we deferred that to Appendix F.3 (page 42) because of the space limitation. On a high level, the proposed procedure aims to find an $\epsilon$ that makes it more likely for the true optimal solution to be included in the "near optimum set", instead of being ruled out by suboptimal solutions. We also kindly refer the reviewer to Figures 4, 5, and 8 in Appendix F.3 for more experiments that compare the algorithm performance under various choices of $\epsilon$. Regardless of potential violation of the conditions, the practical performance of this adaptive strategy is satisfactory.

Q6: Growth rate of $k_1, k_2, B_1, B_2$ to achieve convergence

A: The reviewer is correct that $k_1, k_2, B_1, B_2$ need to grow in a certain way to make the bound vanish. The typical scale of these numbers when applying our method is that $k_1,k_2$ are of the same order, $n/k_1\to \infty$, $n/k_2\to\infty$, and $B_1=O(n/k_1),B_2=O(n/k_2)$.

Q7: In Technical Novelty, the authors mention "a sharper concentration result for U-statistics with binary kernels, improving upon standard Bernstein-type inequalities." I believe the KL divergence type concentration inequality is not new. In D.2, once it comes to the step that $\tilde{\kappa}$ can be viewed as a binomial random variable, the rest is known. The novelty of the work might be the application of this result in U-statistics with binary kernels.

A: The reviewer is correct about the KL divergence type concentration. The novelty indeed lies in the application of this result in U-statistics with binary kernels.

Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.

W1: Significance in going from polynomial to exponential decay

A: It is correct that in classification the widely used cross-entropy loss is inherently light-tailed, but in regression the loss function can be heavy-tailed and our method improves the tail decay from polynomial to exponential. There are existing methods such as MOM and truncation-based methods as discussed in Section 4 that can provide such tail enhancement under certain structural conditions on the model class or for certain types of loss functions, but our method is the first that is free of these restrictions.

Q1: Classification with many classes

A: In classification with infinite number of classes, the distribution of the loss is exactly the distribution of the (minus) log probabilities of the classes. Therefore in theory the loss can be heavy-tailed if the log probabilities are heavy-tailed, but in practice, it may not be that likely for a log value to be heavy-tailed.

W2: Comparison to modern ensemble methods

A: We have added a new set of experiments comparing our approach with popular existing tree ensembles, including Random Forest (RF), Gradient Boosted Decision Trees (GBDT), and XGBoost (XGB). Decision trees are used as the base learner for all methods. Random forests are constructed with the same number of decision trees as our methods to ensure a fair comparison. GBDT and XGB are constructed with early stopping to avoid overfitting. Results on percentiles of the test errors are as follows:

Comparison with tree ensembles in terms of tail performance

For the same synthetic data as described in lines 209-212

• $n=2^{11}$, Pareto shape = $1.5$

• $n=2^{11}$, Pareto shape = $2.0$

• $n=2^{11}$, Pareto shape = $2.5$

For a new synthetic data $Y=10\sum_{i=0}^{9}2^{-i}\sin(2\pi X_i)+\epsilon_1-\epsilon_2$ where each $X_i$ is uniform on $[0,2]$ and $\epsilon_1,\epsilon_2$ are Pareto

• $n=2^{15}$, Pareto shape = $1.5$

• $n=2^{15}$, Pareto shape = $2.0$

For a new synthetic data $Y=10\sin(2\pi X)+\epsilon_1-\epsilon_2$ where each $X$ is uniform on $[0,2]$ and $\epsilon_1,\epsilon_2$ are Pareto

• $n=2^{15}$, Pareto shape = $1.5$

• $n=2^{15}$, Pareto shape = $2.0$

These results show that our methods outperform the base learner in almost all cases, and also outperforms RF, GBDT, and XGB especially in high percentiles when the tail is heavy (e.g., with Pareto shape 1.5). For not so heavy-tailed cases RF, GBDT, XGB may outperform our methods.

Q2: Mixing our method with gradient boosting

A: Thank you for your insightful comments. We greatly appreciate your suggestion regarding integrating our approach with gradient boosting. We agree that using the base learner selected by MoVE/RoVE/RoVEs to replace the plain base learner can possibly strengthen the overall model compared to the two individual approaches. We will carefully consider this mixed strategy in our future study.

W3: Exponentially growing ensemble size?

A: We have rigorouly investigated how the accuracy of the retrieved model set (measured by the excess risk of the best model in the set) scales with the ensemble size $B_1$. Our result (Lemma C.12) in line 1021 shows that in order to retrieve an $\delta$-optimal model with high probability, the ensemble size can be set to the order $O(\frac{1}{1-\mathcal E_{k,\delta}})$. This is straightforward to understand: Each model trained on a random subsample is $\delta$ optimal with probability $1-\mathcal E_{k,\delta}$ by the definition of the excess risk, and if subsamples are approximately independent (e.g, when $k<<n$), the number of subsamples needed to obtain an $\delta$-optimal model is approximately geometrically distributed with success rate $1-\mathcal E_{k,\delta}$. The probability $1-\mathcal E_{k,\delta}$ typically does not approach zero exponentially fast as $\delta\to 0$, so the required ensemble size does not need to increase exponentially.

Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.

Q1: Confusing usage of the term "majority vote"

A1: We will update the relevant part of the introduction as follows. To avoid the confusion between our procedure and the widely known majority vote in ensemble classification, we will no longer quote the phrase "majority vote" at the outset, but first describe the procedure in plain English, e.g., "selecting the model that is most frequently output by the base learner", and then identify it as a counterpart of the widely known majority vote for selecting models (as opposed to classes). This applies to discrete $\Theta$. If the review still thinks it's misleading, we are happy to replace the phrase "majority vote" with more distinguishable terms such as "mode finding" throughout. For general (including continuous) $\Theta$, the vote is preceded by a step that retrieves a finite set of high-quality models to vote on, thereby addressing the "each model appearing at most once" issue in directly copying the procedure from discrete to general $\Theta$.

A short description of the procedure is to select the model that does best on most subsample runs as the review suggests, but the notion of "best" here is determined by what the base learner attempts to optimize. Tie-breaking can be done arbitrarily as mentioned in line 99, and convergence theory is provided in Theorem 2.1.

Q2: Assumptions for guarantees of exponential tails

A2: For our key result Theorem 2.1, the only required technical condition is $\eta_{k, \delta}:=p_k^{\max }-\mathcal E_{k, \delta} > 0$ as stated in line 116. An informal interpretation of this condition is that the base learner generates $\delta$-optimal solutions more often than other solutions (but not necessarily exponentially more often). We choose not to use more specific conditions such as moment conditions on the loss and structural conditions on the model class that imply our condition, in order to 1) make the theorem more general and 2) show a direct contrast between the tail of the base learner and that of our ensemble method. Indeed, our condition will hold for large enough $k$ and $\delta$ as long as the base learner is weakly consistent, i.e., converging to optimal solutions in probability as $k\to\infty$. Weak consistency is a rather weak requirement that does not need finite high-order moments. On the other hand, our explicit bound (10) clearly demonstrates how the tail $\mathcal{E}_{k,\delta}$ of the base learner is improved by the ensemble.

Q3: Cost and scalability of computing

A3: Like other machine learning algorithms, in practice the hyperparameters $k$ and $B$ can be tuned via techniques such as cross validation. On a technical level, the subsample size $k$ controls a tradeoff between the bias and the tail of method: Using a large $k$ in our method does not inflate the bias against the groundtruth but also may not be able to shrink the tail due to the small ratio $n/k$, whereas a small $k$ helps shrink the tail but may enlarge the bias. As for $B$, increasing $B$ typically improves the performance, but our bound also shows a value larger than $\mathcal{O}(n/k)$ does not provide further benefit. We will update relevant discussion in lines 133-138. We also kindly refer the reviewer to Appendix F.3 for our configuration recommendation that works well for most problems we consider in the experiment. Regarding the computation cost in repeated training, we argue that this is common for all ensemble methods, and this is less significant for our method because subsample training are parallelizable. See Figure 7 for an experiments on the effect of $B$ on the performance.

Q4: Comparison to other robust methods

A4: We have provided a comprehensive comparison between our method and robust techniques such as MOM and truncation-based methods in lines 289-303. As discussed there, MOM approaches require squared loss and/or convex function classes whereas our method only relies on the weak convergence of the base learner and thus is free of these conditions. Thanks for pointing out the work Kwon et al. (2021), and in their paper focuses on the squared loss and requires 4-th moment conditions. We will add this reference in the paper.

Q5: Things to think about in the real world and examples of how to use it

A5: The reviewer is correct that our method is most useful for heavy-tailed problems, such as those from finance and physics. We try our method on several real-world datasets from the UCI repo, and found ROVE useful in predicting energy yield for gas turbines and critical temperature of superconductors:

• Gas turbine data

• Superconductivty data

Here we list the percentiles of the test error of the base learner and our ROVE algorithm to compare their tail performance. We run each method multiple times on the data set, and each time we randomly split the data into training and testing and evaluate the trained models on the testing set.

In cases where the problem is not heavy-tailed our method usually perform comparably with the base learner or only brings marginal improvement as demonstrated by our experiments.