Boosting Revisited: Benchmarking and Advancing LP-Based Ensemble Methods
Authors: Fabian Akkerman
Julien Ferry
Christian Artigues
Emmanuel Hebrard
Thibaut Vidal
Venue: Accepted by TMLR ()

Abstract: Despite their theoretical appeal, totally corrective boosting methods based on linear programming have received limited empirical attention. In this paper, we conduct the first large-scale experimental study of six LP-based boosting formulations, including two novel methods, NM-Boost and QRLP-Boost, across 20 diverse datasets. We evaluate the use of both heuristic and optimal base learners within these formulations, and analyze not only accuracy, but also ensemble sparsity, margin distribution, anytime performance, and hyperparameter sensitivity. We show that totally corrective methods can outperform or match state-of-the-art heuristics like XGBoost and LightGBM when using shallow trees, while producing significantly sparser ensembles. We further show that these methods can thin pre-trained ensembles without sacrificing performance, and we highlight both the strengths and limitations of using optimal decision trees in this context.

Published in Transactions on Machine Learning Research (10/2025)
Boosting Revisited:
Benchmarking and Advancing LP-Based Ensemble Methods
Fabian Akkerman
frraklerman@uutentt...
Industrial Engineering and Management Science
University of Twenle
Julien Ferry
julien.ferry@polmmd.cc
CIRRELT & SCALE-AI Chair in Data- Daiten Supply Chains
Polglechnique Montrial
Christian Artigues
christion, ietpstiionartiueseeeeeee Claas.
CNRS Universilé de Toulouse
Emmanuel Hébrard
hebrard
LAAS-CNRS
Université de Toulouse
Thibaut Vidal
Uhibaut vidal@polymalllcco
CIRRELT & SCALE-AI Chair in Dala-Driven Supply Chains
Polytechnique Montréal
Reviewed OpenReview: https: openreview. formmm id= 1scC4P2UR4
Abstract
Despite their theoretical appeal, totally corrective boosting methods based on linear pro- gramming have received limited empirical attention. In this paper, we conduct the first large-scale experimental study of six LP-based boosting formulations, including two novel methods, NM-Boost and QRLP-Boost, across 20 diverse datasets. We evaluate the use of both heuristic and optimal base learners within these formulations, and analyze not only accuracy, but also ensemble sparsity, margin distribution, anytime performance, and hyper- parameter sensitivity. We show that totally corrective methods can outperform or match state-of-the-art heuristies like XGBoost and LightGBM when using shallow trees, while producing significantly sparser ensembles. We further show that these methods can thin pre-trained ensembles without sacrificing performance, and we highlight both the st strengths and limitations of using optimal decision trees in this context.
1 Introduction
Despite the surge in deep learning, ensemble mothods remain stato-of-tho-art for tabular data (Borisov al., 2024). This is evident in recent prediction competitions, where ensemble methods often outperform deep neural networks (Bojer & Meldgaard, 2021; Makridakis et al., 2022; 2024). Among them, boosting methods, such as Adaboost, XGBoost, and LightGBM, have become the default choice due to their efficiency, accuracy, and practical success across domains (Freund & Schapire, 1997; Chen & Guestrin, 2016; Ke et al., 2017). While these methods are widely adopted, they rely on greedy, stage-wise updates that often obscure the optimization principles behind their effectiveness.
A more theoretically grounded alternative offered by linear programming (LP) based boosting methods, which formulate ensemble training global optimization problem. These methods cast training

---

Published in Transactions on Machine Learning Research (10/2025)
linear program solved via column generation (Uchoa et al., 2024), where the goal is to optimize the weights of all base learners simultaneously. At each iteration, new base learner is added to improve classification margins- -tth the signed distances between examples and the ensemble decision boundary. From the perspective of docomposition techniques, column gencration provides a principled framework to decouple the selection of base learners (solutions of pricing subproblems) from the global reweighting of the learner weights (solution of the master problem). These two subproblems are linked through dual variables, which emphasize misclassified points. This iterative reoptimization is referred to as total correctiveness. Notably, variations in the main objective, such as maximizing the minimum margin or minimizing the variance across margins, lead to different selection criteria for the base learners.
Although LP-based boosting was introduced over two decades ago, comprehensive empirical analysis remains limited. While some studies have explored multiple formulations or larger datasets, most remain either narrowly scoped or primarily theoretical. Few works offer broad and systematic comparison of L.P-basdd methods, and even fewer examine their behavior in depth across varying conditions. As a result, key questions remain unanswered: how do different formulations behave in practice, how do they compare to modern heuristic methods, and how are they affected by factors such as tree depth, margin objectives, and the use of optimal versus hcuristic base learners?
In this work, we conduct the first large-scale empirical study of totally corrective boosting methods. Focusing on binary classification tasks, we compare six optimization based methods, which we refer to as LP-based for brevity, although some involve quadratic programs (QPs). This includes two novel formulations introduced in this paper. Their performance is benchmarked against three sfate-of-the-art heuristic boosting baselines. Our evaluation spans 20 benchmark datasets and explores wide range of settings, encompassing varying tree depths, margin objectives, and types of base learners namely, heuristic CART trees and optimal decision trees. Decision trees are a natural choice in boosting due to their interpretability, and ensemble sparsity is particularly relevant: smaller ensembles with fewer trees are easier to interpret and faster at inference time. Beyond accuracy alone, our goal is to better understand the structure and propertics of totally corrective methods. To that end, we examine anylime performance, ensemble sparsily, margin distributions, sensitivity to hyperparameters, and reweighting dynamics. Our findings provide new insights into why certain formulations generalize better and offer practical guidance for designing interpretable and effective ensemble models.
To summarize, our main contributions are:
We conduct an extensive empirical study across twenty datasets, comparing six LP-based boosting methods and three state-of-the-art heuristic baselines.
We analyze generalization performance, anytime behavior, margin distribution, ensemble sparsity, and hyperparameter sensitivity of LP-based boosting methods.
We study the use of three different types of base learners within boosting frameworks: CART trees with hard voting, CART trees with soft voting through confidence scores, and optimal decision trees.
We present two novel formulations that achieve state-of-the-art performance: one that focuses on the negative margins (misclassificationn)) and another that adapts an existing method by introducing a new quadratic regularization term.
The full source code is available under an MIT license at https://githrn http://gittuub.oofffaaaaaea colboost. All methods are implemented in the unified, user-friendly colboost Python library to promote more systematic empirical comparisons between totally corrective methods and facil- Furthermore, all
itale future research in this field, see https://pypd https::/pppi.oor//rrojeee org/projjet//ooloosttt experimental results and datasets used in this study can be found at https btops:///of http://i....////////// 10. /412//
The remainder of this paper is organized as follows. Section introduces notation and background on boosting approaches. Section reviews related work on totally corrective methods and highlights our contri- butions. In Section& 4, we present two novel totally corrective formulations. Section 5 details our experimental
2

---

Published in Transactions on Machine Learning Research (10/2025)
design. The results are then reported in two parts, based on the type of base learner. Section 6 focuses ensembles built with CART trees, using either hard voting or confidence-based soft voting. Section 7 then evaluates the use of optimal decision trees. Finally, Section 8 concludes this paper.
2 Preliminaries
Let D {(11,,11 (22, v2)...., (IM. ym)} be a dataset of size M where each example (also called data point, or sample) 2; E has a binary label y E {-1,1). Also, let H {h, .2,...,.y ,,r] be an ensemble of classifiers, such that hy : X + {-1,1}, Vj [I....,T} T). Boosting methods usually associate weights .......,yy wT) } to the different classifiers -asso called base learners weak learners- to minimize w (w), u.,...,, classification error. Base learners are trained iteratively such that each new classifier h2 is fitted using sample weights u, = {uy1. My2,.... UyM }, which highlight misclassified points. In column generation- canerattoo-bbsed methods, the weights w are either computed directly (in primal) or derived from dual variables, depending on the formulation. While totally corrective boosting methods are able to recompute the base Iearners' weights w to maintain the best-performing ensemble al each iteration, popular heuristic methods typically compute the weight of each classifier only once and never update in further iterations.
Adaboost, introduced in Freund & Schapire (1997), is classical hcuristic boosting method. Its most common version relies on the SAMME algorithm (Hastie et al., 2009). For a pre-specified number of iterations T, which specifies the number of trees that will be used in the ensemble, the SAMME algorithm iteratively does the following. First, (i) it trains a tree using sample weights uj to weight datapoints for importance (in the first iteration, U1s < 1 Vi E {I....,My MM), next, (ii) the weighted error the new tree hy is calculated, and (iii) the weight wy of the new tree the ensemble voting process is determined based on its error. Afterwards, (iv) new sample weights uj+1 are calculated by updating the former ones u, based the misclassifications of the new tree hy and pre-defined learning rate hyperparameter, and the process continues at step (i) until T trees have been added to the ensemble.
M
Totally corrective methods are different from Adaboost in several ways. We present a high-level and generic overview to summarize these distinctions in Algorithm (see also Shen et al. 2013). The key differences from Adaboost (and other heuristic boosting methods) are: (i) the ensemble size is not pre-defined, as the stopping criterion, based on the dual constraint, ensures that the optimal ensemble has boen found, (ii) intermediate error term is calculated to determine the weights and u, as both from the LP, and (iii) the weights w re-computed at each LP solve (instead of only the weight of the new tree). These differences offer clear advantages over heuristic boosting methods like Adaboost, as the stopping criterion is well-defined ensuring finite termination at global optimum, sample weights u are determined using the complete current ensembles' performance, and all base learners' weights w are re-determined, which yields ensembles that perform better while also being sparser (with fewer trees).
outputs
Algorithm High-level totally corrective boosting algorithm
Require: Convergence threshold 6 1 1: Ei (I..M,, un + M 8 0 j+1
b Initialize the variables
while True do
Fit new tree hy to training data using weights uj if EM (x, S 3 e then break
Solve the pricing problem
Check for stopping criterion
Add hy to the master problem Obtain new voting weights Wye(1..))) and compute uj+1 Solve the restricted master problem
return A convex combination of base learners and voting weights
3
Related Works
In this section, we focus on totally corrective boosting methods for training ensemble models. A foundational contribution comes from Grove & Schuurmans (1998) who, motivated by the success of Adaboost. (Freund
3

---

Published in Transactions on Machine Learning Research (10/2025)
& Schapire, 1997) and the hypothesis that its effectiveness arises from focusing margins (Bartlett et al., 1998), propose the use of LPP to minimize the worst-case margin. In classification, the margin typically quantifies the confidence of the ensemble's prediction: it is the difference between the cumulative vote assigned to the correct label and the largest cumulative vote assigned to any incorrect label (Bartlett et al., 1998). A negative margin indicates a misclassified example -one that lies on the wrong side of the ensemble's decision boundary. Grove & Schuurmans (1998) propose the following LP formulation (notation adapted for consistency):
maximizew.p p.
(1)
subject to y1 Σ
wihh((r))2
-i= I......, M, 2.
(2)
W 1,
(3)
j=1
" 2 0,
Vj = I....,T.
(4)
where o is the minimum margin, the term yi Eド= wj (I,)) is positive when the current ensemble votes correctly for data point (x), and negative when the ensemble vote is incorrect. The sum of weak learner weights is bounded by 1. Solving this problem using a column generation framework provides two main advantages: (i) it allows leveraging the dual solution to identify new weak learners at each iteration, and (ii) it offers a well-defined stopping criterion. The corresponding dual problem is given by:
T
minimize,.08
B.
(5)
M (n;h SB, Vj = =j=1.... I...,,
subject to
(6)
M
= 1,
(7)
1=1
0
S U/ 11=1.... M.
(8)
In this dual formulation, Constraint (6) defines the misclassification costs u; for each example i, emphasizing those with low or negative margins. Training a weak learner corresponds to finding a violated constraint (6) and new variable wy of positive reduced cost. Furthermore, when no base learner satisfies ΣØ=1 B, the current combined classifier represents the optimal solution among all possible linear combinations of base learners. Despite these propertics, Grove & Schuurmans (1998) report unstable empirical performance for this L.P. Demiriz et al. (2002) address several of the issues by using a soft-margin LP variant, i.e., introducing a slack variable in Constraint (2). This adjustment improves robustness: unlike the hard-margin formulation, which can be highly degenerate when the number of weak learners is small relative to the number of data points, the soft-margin version reduces such degeneracies and is less sensitive to noisy outlier data. The resulting formulation known as LP-Boost- alleviates many limitations of the original hard-margin LP, though, as we will demonstrate in our experiments, it does not resolve all of them. In the remainder of this section, we discuss the contributions to ensemble learning using linear programming after LP-Boost. (Grove & Schuurmans, 1998; Demiriz et al., 2002).
M u.Hhh >
Theoretical analyses have identified fundamental limitations of LP-based boosting and guided the design of improved formulations. Shen & Li (2009) analyze boosting algorithms through the lens of their La- grange duals, drawing connections between LP-Boost and catropy-maximizan that Adaboost, LogitBoost, and soft-margin LP-Boost can be viewed as entropy-regularized variants of the hard-margin LP-Boost formulation. A key insight from their analysis is that LP-Boost, despite its focus on maximizing the minimum margin, often exhibits inferior generalization performance compared to al- gorithms that optimize for average margin or margin distribution, such as Adaboost. The authors argue that entropy regularization, which enforces a more uniform weight distribution on training examples, con- tributes to Adaboost's 's superior generalization performance, especially in noisy or non-separable datasets.
frameworks. They show
4

---

Published in Transactions on Machine Learning Research (10/2025)
This work provides theoretical insights into why LP-Boost's strict focus on the minimum margin may limit its effectiveness in practical settings, a conclusion further supported by the formal results in Gao & Zhou (2013).
Building on earlier theoretical insights, several works have proposed totally corrective variants of LP-Boost to improve both convergence and generalization. Warmuth et al. (2006) propose Total-Boost, which incorpo- rates entropic regularization and adaptive margin constraints achieve logarithmic convergence guarantees. The authors experimentally demonstrate that Total-Boost often requires significantly fewer itcrations than LP-Boost, particularly in high-dimensional or redundant feature spaces, while producing smaller ensembles, making it advantagoous for fcature selection tasks. Total-Boost. serves as a precursor to Soft-Boost (Rätsch et al., 2007), which extends the approach to the non-separable case by minimizing the relative entropy to the initial distribution, subject to linear constraints on the edges of all previously generated base learners -where the edge is defined as the weighted difference between correctly and incorrectly classified exam- plcs. Rätsch et al. (2007) show that LP-Boost may require up to (M) itcrations to converge in the worst case, particularly when the problem structure induces linear dependencies in the optimization process. In contrast, Soft-Boost's use of capping constraints and entropy updates leads to provably faster, logarithmic convergence, making it a potentially more efficient alternative in such settings. However, its conservative musstrain-ttighening can result in worse early-stage generalization performance.
To address this, Warmuth et al. (2008) introduce Entropy Regularized LP-Boost (ERLP-Boost), which modifies LP-Boost by incorporating a scaled relative entropy term into the objective. ERLP-Boost matches the performance of LP-Boost and Soft-Boost but offers faster early error reduction and guarantees conver- gence within O In ) iterations, with C. being tunable parameter. Additionally, Warmuth et al. (2006) observe that LP-Boost's 'ss empirical performance is sensitive to the choice of the solver: interior-point methods achieve faster convergence than simplex methods in certain scenarios.
More recently, Mitsuboshi et al. (2022) offer a unified view of LP-based boosting methods by framing LP- Boost and ERLP-Boost as instances the Frank Wolfe algorithm. They highlight a key trade-off: LP-Boost has low per-iteration cost but may require many iterations, while ERI.-Boost. converges in fewer steps at a higher computational cost per iteration. To balance these strengths, they propose MLP-Boost, a hybrid algorithm that alternates between LP-Boost and ERLP- Boost steps. Experiments show that MLP-Boost retains the convergence guarantees of ERLP-Boost while achieving runtime comparable to LP-Boost.
Building on the limitations of focusing only on the minimum margin, a line of research has emerged to optimize the entire margin distribution. Shen & Li (2010) introduce MD-Boost, a totally corrective boosting algorithm that, simultaneously maximizes the average margin and minimizes margin variance. Extending L.P- Boost, MD-Boost retains the column generation approach but adopts a quadratic programming formulation, enabling it to overcome limitations inherent to linear programming methods. Empirical results show that MD-Boost outperforms LP-Boost in generalization performance on several benchmark datasets. The authors highlight that MD-Boost's 's ability to consider the full margin distribution, rather than focusing solely on the minimum margin like LP-Boost, contributes to its robustness and improved classification accuracy. In a similar spirit, Roy et al. (2016) propose Cq-Boost, a column generation algorithm that minimizes the PAC- Bayesian C-bound, explicitly accounting for both the mean and variance of the margin distribution. Unlike LP-Boost, which focuses on minimizing the margin of misclassificd points, Cq-Boost leverages quadratic programming to optimize the margin distribution while achieving spanser ensembles. Empirical results show that Cq-Boost outperfrmss I.Pstoost in terms of accuracy and sparsity.
Bi et al. (2004) extend LP-Boost by developing CG-Boost, constructing sparse mixture-of of kernels models. By 2-norm regularization, CG-Boost produces models that balance expressiveness and sparsity, achieving improved generalization and reduced testing time compared to single-kernel or composite-kerun kernel methods. The approach generalizes LP-Boost to quadratic programs, enabling its application to a broader range of learning formulations. Experiments demonstrate CG-Boost's effectiveness in achieving high accuracy with fewer basis functions, outperforming standard composite-kernel methods in both performance and efficiency. Shen et al. (2013) propose CGBoost (not to be confused with CG-Boost by Bi et al. 2004), fully corrective boosting framework that generalizes LP-Boost to accommodate arbitrary convex loss functions and regularization terms (e.g., é1, l,. and fo -nomms) Unlike .ooott,
couum--generation boosting framework for
mixture-of-eerelss
5

---

Published in Transactions on Machine Learning Research (10/2025)
which solves the dual problem, CGBoost focuses on the primal problem, offering simpler optimization with faster convergence. The authors demonstrate that CGBoost effectively balances sparsity and generalization, outperforming LP-Boost in terms of computational efficiency while maintaining or improving classification accuracy across various benchmark datascts.
To address class imbalance, Datta et al. (2020) propose LexiBoost, a lexicographic programming- based boosting framework that eliminates the need for manual cost tuning. LoxiBoost solves a two-stage sequence of linear programs, first minimizing hinge loss separately for each class, then minimizing the deviation from these losses to balance misclassification rates. The dual formulation further adapts instance weights dy- namically. The approach is scalable to multi-class settings and demonstrates strong performance across imbalanced datasets, hyperspectral images, and ImageNet subsets, outperforming traditional cost-sensitive boosting methods. Aziz et al. (2024) propose a dynamic data-reduction ensemble learning algorithm (DDA) that extends LP-Boost. by incorporating dynamic data selection, phased learning, and nonlinear loss func- tions. Unlike standard LP-Boost, which considers the entire training dataset in every itcration, DDA uses sparse dual solutions to identify "active data points" in a bootstrap fashion, focusing compulation on subsets of critical examples to improve efficiency. The algorithm operates in three phases: initialization (bootstrap- ping base learners), generation (error-based sampling without full master problem inputs), and refinement (iteratively adding base learners based on active data subsets). By incorporating nonlinear loss functions and explicitly promoting diversity, DDA reduces generalization error while maintaining or improving computa- tional efficiency. Experiments show that DDA outperforms standard LP-Boost by achieving higher accuracy and better diversity in ensemble models.
Other work has adapted LP-Boosting for specific application domains different base learners. Hinrichs et al. (2009) propose spatially augmented LP-Boosting, adding spatial smoothness constraints to promote contignous regions in medical imaging data. Applied to the ADNI dataset, the method improves clas- sification accuracy and interpretability compared to standard LP-Boost, achieving better generalization performance. Aglin et al. (2021) invostigate optimal forests of decision trees by integrating optimal decision free (ODT) learning into LP-Boost and MD-Boost. frameworks. Their method, OptiBoost, uses a column generation process with ODIs to guarantee optimality for both LP-Boost and MD-Boost formulations. Experiments demonstrate that optimizing the entire margin distribution with MD-Boost often yiclds better generalization compared to maximizing the minimum margin in LP-Boost. The study highlights that incorporating ODTs into boosting frameworks not only improves optimization objectives but also leads to more accurate and sparse models, outperforming heuristic approaches on certain datasets.
To sum up, most works on totally corrective boosting propose formulations that optimize the margins of base learner ensembles. However, key aspects of LP-based boosting including the ensemble accuracy- sparsity trade-off, anytime behavior, and sensitivity to hyperparameters- remain underexplored. In this work, we address these gaps through a comprehensive empirical study across twenty datasets, comparing six LP-based boosting methods against three state-of-the-art heuristic basclines. Our results provide a systematic understanding of how margin formulations affect not only final accuracy but also convergence speed, sparsity, and hyperparameter sensitivity. In addition, we study the influence of weak learner choice voting, and optimal
comparing heuristic CART trees with either hard voting or soft (confidence-baase) decision trees- on boosting performanco. We also introduce two novel formulations. The first one explicitly models negative margins, allowing direct control of the trade-off between generalization performance and training accuracy through regularization hyperparameter. The second applies quadratic regularization to improve ensemble stability. Together, these contributions offer both practical insights and theoretical extensions that strengthen the foundation of LP-based boosting research.
4 New Totally Corrective Formulations
We introduce two novel boosting formulations that build on existing margin-based approaches. The first focuses on a previously underexplored aspect of the margin distribution, the negative margins. This formu- lation, detailed in Section 4.1, directly yields the ensemble weights w from the primal solution, while the sample weights are derived from the dual. The second formulation, presented in Section 4.2, introduces
6

---

Published in Transactions on Machine Learning Research (10/2025)
regularization on the sample weights u, which computed directly in the primal to keep the quadratic term in the objective. In this case, the ensemble weights w are recovered from the dual solution.
4.1 Negative Margins Boosting
The idea behind this formulation, which we coin Negative Margins Boost (NM-Boost), to maximize the sum of all margins while assigning greater weight to negative margins in the objective. coefficient C controls the trade-off between reducing negative margins (which serve proxy for misclassifications)) and increasing the overall sum of margins (which promotes better generalization). NM-Boost avoids the limitations of earlier approaches that focus solcly on the worst-case margin -often overly sensitive to outliers- as well as the drawbacks of LP-Boost, where the margin of each example is decomposed into a "slack" and worst-case margin, making the contribution of individual examples difficult to interpret.
In the primal formulation shown below, variables p. represent the negative part of the individual margins: Pi p 0 if example correctly classified, and p; pe is the (negative) margin Pi between the ensemble's prediction for misclassified example and the decision boundary (minus a small offset. otherwise. Negative margins hence receive greater penalization in the objective function. This explicit modeling ensures that mis- classified examples (with negative margins) directly infiuence the optimization, rather than being absorbed implicitly in the overall margin sum. In practice, they are computed as the negative part of the margins offsct by a constant term 7. This offset ensures a clear distinction between zero and strictly positive margins, since in the former case, an example may not be confidently classified depending on the Lie-breaking policy used. Note that this offset becomes tight when all trees contribute equally the vote." 1 The optimization problem of NM-Boost is formalized as:
M Σ
M
maximizew.p.pmm
p
neg
C
Σ
Pi
(9)
subject to y: wj
wrhh(I;) 2 Ps: Vi I=..,.,,M M,
(10)
j=1
Pi neg
S
Vi = 1, ,,.., M,,
(11)
P3
neg
< P:
T
Vi = I.....M. M,
(12)
T
Σ wy 1, j=1
wj 2 0,
Vj I...,, T.
(13)
Because (9) is LP with constrained to the probability simplex, an optimal solution can be chosen to place weight on only subset of base learners; in practice many wy are zero.
4.2 Quadratically Regularized LP-Boost
We also propose a boosting formulation with a quadratic regularization term, which we call QRIP-Boost. The formulation builds on prior work by Warmuth al. (2006), Rätsch et al. (2007), and Warmuth et al. (2008). More precisely, we modify the objective function of ERLP-Boost, whose formulation is provided in the Appendix B.3. The original ERLP- -oost ensures stability through entropy-based smoothing. Moreover, it requires iterative refinement of the sample weight distribution, repeatedly computing KI-divergence ad- justments and stabilizing small weight changes. In contrast, our proposed QRLP-Boost introduces a direct quadratic regularization that blends entropy and variance-like penalties, enabling larger, smoother updates within a single optimization step. This leads to a more numerically stable process, as the regularization naturally controls weight shifts without requiring repeated ro-optimization or entropy-based corrections.
Our approach differs from FRI.P-oosst in the following ways: (i) instead of minimizing KT-ddvergence penalty, we use combined entropy quadratic regularization term that stabilizes updates while offering more
For instance, this usually the case within a confidence-based soft voting scheme.

---

Published in Transactions on Machine Learning Research (10/2025)
flexibility in reweighting training examples, (ii) the weight distribution is updated directly in single QP solve per iteration, avoiding multiple re-solves with adjusted entropy terms, and (iii) convergence is checked based on the QP objective, eliminating the need for iterative entropy-based margin estimates or auxiliary thresholds. QRLP-Boost therefore solves the following convex optimization problem:
M
uf 2n
minimizeu,g
Ug log uf +
(14)
1
subject to
Σ (x))
S Ec. -j= l....., T,
(15)
M
Σ i=1
U4 = 1,
(16)
u4
Vi = 1 ,...,,M M. C
(17)
Here, 17 is defined as max, In M/ MM where esto is small constant. The term un denotes the initial sample weight distribution, typically uniform. The quadratic regularizer / replaces the KL-divergence term in ERLP-Boost, serving to penalize sharp deviations from the initial weights. The quadratic component of the regularizer (with up > 0) makes the objective strictly convex in u, hence the minimizing u is unique. We solve the program directly with a standard convex optimizer; no generic closed-form expression is available. All other constraints are retained from the original GRLP-Booss formulation (see Appendix B.3).
5 Experimental Design
To obtain robust and generalizable insights into boosting with column generation methods, conduct an extensive empirical study across 20 diverse datasets from widely used benchmark repositories in machine learning. These datasets were selected to ensure diversity in terms of size, feature dimensionality, and class balance. A complete description of the datasets is given in Appendix A.
Our study includes the following totally corrective methods, evaluated in the original versions proposed by their respective authors: LP-Boost (Demiriz et al., 2002), CG-Boost (Bi et al., 2004), FRLP-Boost, (orssttWoa (Warmuth et al., 2008), MD-Boost (Shen & Li, 2010), well Boost (introduced in Section 4). For LP-Boost, we adopl the formulation from Equation 2 in Demiriz et al. (2002), as we found the alternative version (Equation 4) to be highly sensitive to its hyperparameters and more prone to degeneracy. The detailed mathomatical formulations of all totally corrective mothods are provided in Appendix B. While we initially included Co-Boost (Roy et al., 2016) in our experiments, we did not retain in our final analyses for the sake of brevity, as it did not provide additional insights or accuracy improvements over other methods. For comparison, we also include three widely used heuristic boosting baselines: Adaboost (Freund & Schapire, 1997), XGBoost (Chen & Guestrin, 2016), and LightGBM (Ke et al., 2017).
two novel formulations, NM-Boost and QRLP-
To ensure a fair comparison between the different methods, we conduct hyperparameter tuning for which we vary the trade-off parameter C. (totally corrective methods) and the learning rate (heuristic boosting meth- ods) across 10 possible values. Appendix C details the hyperparameter ranges considered for each method, consistent with the original papers' recommendations and refined based on our preliminary exporiments. As each method involves tuning a single hyperparameter only, an exhaustive sweep over a fixed set of values is straightforward and ensures that we reliably measure performance across the relevant range.
Each datasct is split into 60% for training, 20% for validation, and 20% for testing. We select the best- performing hyperparameter value in terms of accuracy using the validation data, and report only the results on the testing data. For all results, we report averages over five random seeds, accounting for variability in data splits and method-specific randomness. We impose a time limit of 45 minutes and an itcration limit of 100 for all the methods. Early stopping is explicitly disabled for totally corrective approaches to ensure that all boosting strategies evaluated under comparable number of iterations. This setup ensures
8

---

Published in Transactions on Machine Learning Research (10/2025)
fairness, each method is allowed to construct ensembles with the same mumber of base learners. In practice, the iteration limit is reached much more frequently than the time limit, which is seldom binding, In Appendix D.I, we report the computational times per dataset for all studied methods. On average, the totally corrective methods require between and 15 minutes of training time, whereas the hcuristic variants typically finish within seconds. Although this represents a noticeable difference, the running times remain modest and well within practical limits for offline training-
All code is written in Python and experiments are executed a Limux cluster using Python 3.11. Mathe- matical programs are solved using Gurobi 10.0.1. We rely the scikit-learn library (Pedregosa et al., 2011) to build CART trees and fit. Adaboost ensembles, and use the Blossom library for optimal decision trees (Demirović et al., 2023). XGBoost and LightGBM ensembles are fitted using their respective Python libraries, see Chen & Guestrin (2016) and Ke et al. (2017), respectively. We run individual experiments on a single thread of compute node equipped with AMD Genoa 9654 cores @2.4GHz along with 2 GB of mem- ory per thread. All totally corrective methods are implemented within the unified, user-friendly colboost Python library, available under an MIT license at
The remaining experimental sections in this paper are organized as follows. Section 6 analyzes the results of ensembles built using CART trees with either hard or confidence-based soft voting. Section 7 then focuses on the use of optimal decision trees in boosting ensembles.
6 Experiments with CART Trees as Base Learners
In this section, we conduct experiments using CART trees as base Icarners -the default choice in most boosting applications due to their computational elficiency and reasonably strong predictive performance, despite being heuristic rather than optimal. Our goal is to provide comprehensive empirical analysis of totally corrective boosting methods, comparing different mathematical formulations with cach other and with the stale-of-the-arl heuristic benchmarks. To this end, we evaluate multiple facets of model behavior: accuracy-paarsity performance (Section 6.1), anytime performance (Section 6.2), ensemble sparsity (Sec- tion 6.3), margin distributions (Section 6.4), and sensitivity to hyperparameters (Section 6.5). We also include an experiment, Section 6.6, for which we obtain an ensemble using an external method (Ad- aboost) and next let the totally corrective methods reweight, the complete ensemble in single shot. All main experiments are conducted using hard voting scheme (i.e., each tree casts vote of either -1 or +1), In Section 6.7, we investigate the impact of adopting soft voting mechanism, in which trees contribute confidence-weighted scores (i.e., each tree votes in the domain []), Throughout all experiments, we vary the maximum tree depth between (decision stumps), 3, 5, and 10. While decision stumps are commonly used in boosting due to their high bias and low variance, we broaden the scope to thoroughly compare performance across varying tree complexities.
6.1 Accuracy-Sparsito Performance
We evaluate the trained ensembles using two metrics: testing accuracy and number of columns (base learners) used. The latter serves as a mcasure of sparsity, indicating how many trees contribute non-zero weight to the ensemble's prediction. Sparser ensembles are generally preferred, as this improves interpretability and reduces inference time.
Figure 1 summarizes all results by showing the average testing accuracy and sparsity across all considered datasets?, for each method and different tree depths. For depth (decision stumps), we observe that NM- Boost, QRIP-Boost, CG-Boost, and XGBoost achieve comparable accuracy. However, NM-Boost matches slightly outperforms the others while using significantly fewer trees. MD-Boost yields the sparsest ensembles but suffers from the lowest accuracy. Interestingly, for decision stumps (which are often the default weak learners of boosting approaches), totally corrective methods outperform the heuristic baselines (Adaboost, XGBoost, and GBM) in both accuracy and sparsity. At depths 3 and 5, some totally corrective methods
While averaging across datasets may seem countcrintuitive, since the resulting metrics lack a clear, interpretable meaning any individual dataset, it is widely used approach for summarizing and comparing methods (see, egg., Freund & Schapire 1996, Demirović et. 2023).
9

---

Published in Transactions on Machine Learning Research (10/2025)
Test Accuracy Fnsemble Sparsity Depth
Accuracy vs Ensemble Sparsit Depth
NM-Boost
XGBoost
QRLP-Boost
CG Boost
XGBoost
NM-Boost . LP-Boost
lightGBM
1.5
Aucrage Tosking Accuro)
l
Averaee Teating Acrurerry
Adaboost CG BooKt
LP--ooost
0.00
Adaboost
ERLP-Boost
Q PRLP-Boost
0.00
ERLP-Boost
9.10
MD-Boost
.MD-Boost
Number Columes
Number Columnz Used
Test Accuracy vs Ensemble Sparsity on Depth
Test Accuracy vs Ensemble Sparsity on Depth 10
NM IMM-Boost
XoBoost
XCBeost MiOEGGMM
6.00
Adaboost CG-Boost
Adaboost
Avcrage Rezting Rccuracy
QRLP-Boost
CG-Boost
Roweage Texting Accuracy
3.525
LP-Boost
2,00
ERLP-Boost
* -NM-Boas.
QRLP-Boost
-ERLP-Boos!
0.000
Boost
-4D 14D-Boost
LP-Boost
25
Average Number Eokemns
Average Number of Eokmns Used
Average testing accuracy compared to average ensemble sparsity over all datasets for CART decision trees of depth 1, 3, 5, and 10.
Figure/ 1:
(NM-Boost, QRLP-Boost, LP-Boost) exhibit close similar accuracy the hcuristic benchmarks but use fewer trees, or find similar accuracy with the same number of trees (CG-Boost). For depth 10, the individual trees are strong and specialized, and using them all is the best policy. As a result, totally corrective methods fall short in accuracy, though CG-Boost remains competitive, partly due to its use of denser ensembles.
Observation With shallow to moderately deep CART trees, lotally corrective methods match or exceed the test accuracy of heuristic baselines while yielding signéficantly sporser ensembles.
Observation 2
Among all totally corrective methods, our proposed NM-Boost achieves the best performance when using shallow to moderately deep CART trees.
Observation With deeper CART trees, a trade-off becomes apparent: heuristic methods achieve generally higher accurney, but al the expense of sparsily.
To allow for more muanced assessment of each method's strengths and weaknessos, we also report per- dataset results. Tables 1 and 2 detail the lesting accuracy and sparsity across all considered datasets, totally corrective methods, and heuristic benchmarks for CART decision tree base learners of depth and 5, respectively. Results for the other depth values are provided in the Appendix D.2, and are consistent with our main observations.
Focusing depth-1 trees (Table 1), observe that the superiority of totally corrective methods over state-of-the-art heuristic boosting approaches, which was previously observed on aggregate results, holds consistently across datasets. The proposed NM-Boost and QRLP-Booss are particularly competitive in this regime.
Observation With decision stumps base learners, the totally corrective boosting methods consistently oulperform or match the benchmarked heuristic appronches on 19 out of 20 datasets.
10

---

Published in Transactions on Machine Learning Research (10/2025)
Table 1: Testing accuracy and number of non-zero weights for different boosting methods using CART trees of depth 1, averaged over five sceds. Bold highlights the best overall accuracy, while star* marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
qute-Boo Boor
Le Boon
CG:Deart
ERLE Boot
MDD-eee
XGDlaat
CAA
Asc.
Old.
Cid..
Asc.
Cokb
beauu
LM0.2
6.79 E063
0482 1.333
3536 0.85
8775
160
8.899:
dahutee
1375 1.133
E200 100)
6712. E/01
030 0825
1
6373 6.337
3T5 6.63
30
170
140
6N0. 6.00
370
0378
(.15
18
GETEAD cudd
27982-002
0008 3031
18
(UK 1.131
3760
CM0 2.405
lauge
31
E46
112 1187
UMIE 1:80
345
01. 11:0
63
1082" 2134
6307 1/81
(000 190
18
1000 9:34
1927 11
35
5-8L-
180
20
11:0
18
35022000 0855
004811:00 3-3011
(M6 6003
0001 088
14
0501 6303
1021 2064
19802
160
0355 8001
300
0208 (31
1700
076
639
3031
0,99 5/00
083
vendeen
L499
0,6
0373
160
EXICH 1163
1511 118
15
180
8308
0121 1800
14
6760 1/63
0331 1980
115
1731 900
180
0 8:65
34
18
0354
EXIT 0.84
1273
0204 086
0353
31N 1185
900
07%:
0179 C19
Observation 5 With decision stumps base learners, NM-Boost and CRLP-Boost achieve the best perfor- mances of all totally corrective methods, with NM-Boost producing sporser ensembles.
Table 2: Testing accuracy and number of non-zero weights for different. boosting methods using CART trees of depth 5, averaged over five seeds. Bold highlights the best overall accuracy, while a star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
N50. Heak
MIn Bork
Arabom!
SCChook
6247 816
8337 1140
22
118 0442
3.3
1751 1448
180
6.774
083
1.0
0.99 8121
32
2.8
12
160
8.00-
130
1307700 3015
15
31
0004
138
0002-000
180
130
0007
1 1000
430-110 10.
60
100 080
112 000
11
1:00 100
190--008 14
110
6/M 088
130
1007 000
18
6.0 11.
0000
0061
1.00
130
1195
631 175
6593 00.9
199 0819
19111005
338
0855 2001
EN0 2005
180
1961200 08.0
130
18
030 1121
4.71 1017
35
0825
23
238
15.2 100
110--917
0/22 0139
130
K:01
1 1100
130
0104 (110
14T=100
10
11
149-009
110
1008 0188
190
1008 -190
KEplUTTaE CASELS
AT8 1089
626
6,55 1084
130
0.23
1101
1701 -00
10
178 -181
178 000
(31 1::0
120 100
17
17K-000
110
178 11.0
130
6378 -1
18
0.999 1 1300
01
1.67 308
11
1597 CKK
11
05991 100
0305 10
19
6X0 1006
01
1961
18
0068 1 0800
130
6099 1099-100 6.0
18
As the depth of the decision trees increases, we observe a shift in the relative performance of the boosting methods. Table 2, which reports results for depth-5 trees, illustrates this trend. These findings suggest that deeper trees tend to favor traditional heuristic methods such as XGBoost and GiM. hevestheless, totally corrective methods -NM-Boost in particular- remain competitive, especially in terms of the trade- off between testing accuracy and eusemble sparsity. This pallern becomes even more apparent for 1epth-10 trees (Appendix D.2): as tree depth increases further, the trade-offs between ensemble size and accuracy grow more pronounced. We observe a gradual increase in the testing accuracy of the benchmarked hcuristic boosting methods as tree depth increases. Nonetheless, for most datasets, the difference relative to the totally corrective boosting methods remains statistically insigníficant, while the latter consistently yield much sparser ensembles. Specifically, for depth-5 trees, only 3 out of 20 datasets showed statistically significant improvement in testing accuracy of heuristic methods over totally corrective ones. For depth-10 -00 trees, this number increased slightly to 5 out of 20. In contrast, the totally corrective methods significantly outperformed the heuristic ones on 1 out of 20 datasets for both depths.
Obscrvation As the depth of decision trees increases, the relative accuracy of totally corrective boosting methods declines compared to heuristic ones. However, on most datasets, differences in testing accuracy are not statisticnlly significant, while totally corrective melhods consistently produce much sporser ensembles.
11

---

Published in Transactions on Machine Learning Research (10/2025)
Observation 7 NM-Boost remains the most accurate totally corrective boosting method with depth-8 and depth-5 brees. With depth-10 10 trees, CG-Boost and ERLP-Boost match its accuracy but produce significanlly larger ensembles.
6.2 Anytime Performance
We now evaluate the anytime performance the different boosting methods, i.e., how their testing accuracy evolves over the iterations. To maintain readability and conserve space, we present results for two represen- tative datasets and a focused subset of methods. The remaining results follow the same trends (in particular, supporting all our drawn observations) and will be released alongside our source code.
Figure 2 shows the testing accuracy of the considered boosting approaches at each iteration -ic.,, after the the image dataset, across different decision tree depths. We observe
addition of each new base learner that performance differences are more pronounced for shallower trees (e.g., depth 1) and tend to diminish as tree depth increases (e.g., depth 10). This suggests that the strategy used to generate and aggregate base learners has a greater impact when the individual learners are weak.
Observation Differences in anytime performance between boosting approaches are most pronounced when using shallow trees. With decision stumps, totally corrective methods significantly outperform heuristic meth- ods especiolly Adaboost during the early iterations.
Furthermore, in the early iterations, totally corrective methods outperform the heuristic benchmarks. This trend is reversed on the ringnorm dataset (Figure 3), where XGBoost and LightGBM consistently outperform the totally corrective methods across all tree depths except depth 10. These results suggest that the ability of cach boosting approach to accurately fit the data in carly itcrations is dataset-dependent, Interestingly, even when using deeper trees, totally corrective boosting methods often yield better performance in early iterations, although heuristic methods tend to catch up quickly
learners added.
NM-Boost
QRLP-Boost
LP-Boost
Adaboost
XGBoost
lightGBM
mage
image
Teetngg
Darot ors
laancioss
Depth 10
2.34
0.5
2.50
0.5
2.55
0.51
2.30
0.33
Ierocioon
Figure 2: Anytime behavior the image dataset for selected methods (all other methods in gray), for CART decision trees of depth 1, 3, 5, and 10. Error bars indicate the standard deviation over 5 seeds.
12

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
LP-Boost
Adaboost
XGBoost
lightGBM
Depth ringhomm
Depth on ringnomm
0.21
Textbrg ACCUP43
0.33
Depth
Depth 10
0.5
Testrn
6294
Daree o16
Figure 3: Anytime behavior on the ringnorm dataset for selected methods (all other methods in gray), for CART decision trees of depth 1, 5, and 10. Error bars indicate the standard deviation over 5 sceds.
Observation When using deeper CART trees base learners, totally corrective methods often achieve better early-stage performance than heuristic approaches though the latter typically converge to slightly higher final accuracy.
The anytime performance of the boosting approaches may also be influenced by how the individual trees are constructed in the underlying algorithms. Indeed, XGBoost and LightGBM both use custom leaf-wise growth strategy to build their base learners, while all other methods use depth-wise approach (CART) to construct each decision tree. We observe that XGBoost and LightGBM perform significantly worse than the other methods during the initial iterations when using decision trees deeper than decision stumps. Their performance typically catches up to that of the other methods after around 10 iterations. This behavior is illustrated, for example, on the adult dataset, with detailed results provided in Appendix D.3.
6.3 Ensemble Sparsity
We now analyze ensemble sparsity, defined as the number of base learners with non-zero weights in the final ensemble. We exclude XGBoost and LightGBM from this analysis, as they use stage-wise additive boosting with implicit weights. In these methods, each tree contributes to the final prediction through its leaf values, scaled by the learning rate, and all trees remain active the ensemble. Figure presents barcharts showing the assigned weight of each tree across different methods for four representative datasets. The results reveal substantial variation in sparsity across methods. As expected, Adaboost always uses all trees by design, since it is not totally corrective and assigns weights sequentially. Surprisingly, CG-Boost despite being totally corrective method and an extension of LP-Boost with regularization term on the ensemble weights often uses all trees as well. This observation is consistent. with prior findings in Roy et al. (2016) and suggests that
regularization may not sufficiently promote sparsity practice. Other totally corrective methods are able obtain the same or better performance with significantly fewer trees. Notably, NM-Boost, LP-Boost, and FRRP-Boock frequently yield sparse ensembles without sacrificing predictive accuracy. QRIP-Boost occasionally produces sparse ensembles but is less consistent. for example,
13

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Book Pooos-Bost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Adaboost
Acc: 0.819"
Acc: 0.800
Acc: 0.789
Acc: 0.789
Acc: 0.811
Acc: 0.808
Acc: 0.777
Aoc: 0.795
Ace: 0.808
Ace: 0.800
Acc: 0.807
Acc: 0.801
Acc: 0.754
Ace: 0.798
Aoc: 0.943
Acc: 0.943
Acc: 0.943
Acc: 0.946*
Acc: 0.932
Acc: 0.918
Acc: 0.942
Acc: 0.961
Acc: 0.960
Acc: 0.961
Ace: 0.961
Acc: 0.924
Acc: 0.950
Acc: 0.945
Figure 4: Ensemble weights for four datasets (top to bottom: breast cancer, german credit, splice, and twonorm) and depth 1 CART trees for totally corrective methods and Adaboost, over 5 seeds. Bold highlights the best overall accuracy, while a star* marks the best among totally corrective methods.
on the splice dataset, it assigns non-zero weights to all 100 trees. MD-Boost generates the sparsest ensembles overall, but this comes at the cost of noticeably reduced accuracy. NM-Boost consistently produces sparser ensembles than QRLP-Boost as its objective implicitly promotes selecting only trees that perform well.
Observation 10 The methods that structurally return the sporsest ensembles while maintaining competitive accuracy are NM- MM-BBost, LP- Boost, and FRLP-Booss
6.4 Margin Analysis
As mentioned in Section 3, most totally corrective methods, including those proposed in this work, focus on optimizing the margins. In this section, we analyze the cumulative margin distribution the methods on the test data. This allows us to compare not only the proportion of misclassífied instances (i.c., those with negative margins) but also the structure of the decision boundaries induced by different methods.
First, consider the margins of the boosting methods with tree depths of 1, 3, and 5, for various datasets. Figure shows the cumulative margin distributions on the german credit and ringnorm datasets. We observe that the minimum margin of the methods across the depths is not directly linked to test accuracy, echoing the insights of Shen & Li (2010). Similarly, the variance of the margin distribution does not appear to be the primary driver of performance: for example, QRLP-Boos often yields lower margin variance across depths, yet is not always the top-performing method. This supports the doubts raised by Breiman (1999) and further discussed in Gao & Zhou (2013). QRLP-Boost and NM-Boost generally achieve the lowest margin variance, although this difference vanishes with deep decision trees, aligning with the absence of significant performance differences in that regime.
Observation 11 Differences in performance across boosting methods cannot be fully explained by their margin distribution. Methods with a heavy right-lail of the distribution (high confidence on correclly classified data points) not necessarily have the highest accuracy and lowest minimum margin.
Next, we take a closer look at NM-Boost and QRLP-Boost, and analyze how their margin distributions for the test data change for different values of their tradeoff hyperparameter (C). As comparison, we also plot the margin distribution of Adaboost for different. values of its hyperparameter (learning rate). We
14

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Adaboost
XGBoost
lightGBM
gern
Margin ringnorm
Cumulative Danaru
Cundettive Denalyy
E6-
C4
62-
60
Mangin
QRLP-Boost 0.808
QRLP-Boost 0.931
Depth 3 Margin Distributions on german credit
Depth 3 Margin Distributions en ringnorm
Cumuustti Aatre DerGtty
Cumndettin Dernity
-02
04
Scaled Margin
Scaled Margin
NM-Boost
0.878
ORLP-Boost, CG-Boost
0.935
LightGBM 0.881
XGBoost
0.943
Margin Distributions on germ an
Depth Margin ringnorm
Camuistive Dendtt
Camulalive tow Deruity
Scaled 64
34
68
Margin
QRLP-Boost 0.884
NM-Boost 0.942*
LightGBM
0.887
XGBoost
0.948
Figure 5: Test data margin distribution for german credit (left column plots) and ringnorm (right column plots) datasets using CART trees of depths 1, 3, and 5, over seeds. Bold highlights the best overall accuracy, while a star" marks the best among totally corrective methods.
15

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
Adaboost
Depth Margin Distributions NM-Boost on german credit
Depth Margin Distributions NM-Boost on ringnorm
Hyperparameters
Hypprrperameters
04
5e-02
Se-02
1e-01
1e-01
Cumurative Donut)
2e-01
2e-01
2e-01
2e-01
36-01
3e-01
3e-01
Eumudettio
3e-01
46-01
46-01
4e-01
4e-01
Se-01
Se-01
66
Norgin
Margin
Acc.
Acc.
NM-Boost
0.878
NM-Boost
0.934
Depth Margin Distributions ORostBoost german
Depth Margin
CRL ringnom
Hyperparameters
Hyperparameters
0.0076M
0.0068M
Curni Late DerGtt
0207M
Decriiy
0.0201M
0338M
0.0334M
04499M
0.0467M
0. 0.0600M
0.0600M
60
6A
6.6
32
022
0.4
Mangin
Margin
Acc.
Acc.
QRLP-
0.856
QRLP- QRLP-Boost
0.935
Margin
german
Depth
ringnorm
Hyporparameters
Hyperparameters
1e-03
16-03
1c-01
1e.01
2c:01
Cumuratvv Deratu
3e-01
3e-01
4c-01
6e-01
6e-01
7c-01
Cumpletive
Be-01
8c-01
9c-01
1e
1e 00
60
Acc.
Acc.
Adaboost
0.875
Adaboost
0.906
Figure 6: Test margin distribution over the hyperparameter for german credit (left column plots) and ringnorm (right column plots) datasets using depth 3 CART trees, over 5 seeds. The best hyperparameter value is marked bold in the legend. Bold accuracy highlights the best. overall, while star" marks the best among totally corrective methods. The legend's outline color indicates the used formulation.
display in Figure 6 the margin distributions for depth-3 trees, again for the german credit and ringnorm datasets. Remember that for NM-Boost, the hyperparameter C controls the tradeoff between reducing negative margins and increasing the sum of margins. Lower values of C' focus on reducing the negative portion of the margin distribution, thereby minimizing misclassifications, whereas higher values enhance generalization by increasing the positive margins. For QRLP- C controls the balance between the quadratic regularization of sample weights and the original R.P-Boost linear worst-case margin.
16

---

Published in Transactions on Machine Learning Research (10/2025)
For NM-Boost, the hyperparameter has a direct and large effect on the variance of margin distributions: larger values of C' place more emphasis on maximizing the sum of margins (i.e., assigning more weight to confidently classified examples), which leads to a wider spread in margin values and thus higher variance.
For QRLP-Boost, we observe a smaller impact on variance but a more noticeable effect on the smoothness of the margin distribution: increasing C' tightens the upper bound on individual sample weights, effectively increasing the regularization on the distribution. This promotes smoother distributions and moves the objective further from that of standard LP-Boost.
Interestingly, for NM-Boost, lower variance in the margin distribution tends to correlate with better gen- eralization on the test set, which is analogous to insights in Shen & Li (2010). However, this result is not necessarily confirmed by the earlier results in Figure 5. The same goes for QRLP-Boost a smoother curve does not necessarily yield better generalization. we look at the Adaboost margins, this is confirmed, as the best performance is not at the lowest variance margin distribution.
Observation 12 Maryon distribulion variance is not necessorily correlated with lesting accuracy.
6.5 Hyperparameter Sensitivity
We further evaluate the sensitivity of methods to their hyperparameter. To do so, we plot the testing accuracy and number of used columns (as before) but now for all hyperparameter values, instcad of only the best found on the validation data. We hereafler focus two representative datasets, and plot results for all remaining ones in Appendix D.4. Figure 7 shows the performance of totally corrective boosting approaches on the ringnorm and mushroom secondary datasets using depth-1 and depth-5 trees. Across all 20 datasets, we consistently observe a trade-off between sparsity and testing accuracy. The interesting finding is that
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Depth Accuracy vs Columns (ringnorm hyperparams)
Dopth 5 Accuracy Columns gringnarm hyporparams)
14
3.0
C.--
Testina Accurscy
Tweking Accuracy
6.4
C3
46
25
Number Columns
Number of Used
Depth 1 Accuracy Colurns (mushroom secondary hyperparams)
Depth 5 Accuracy vs Columns fmushroom secordary hyperparane
11
30-
Tuzzng Accuas)
Accurety
C.-
05
Number Columns Used
Number of Columns Used
Figure 7: Average testing accuracy compared to average ensemble sparsity over two datasets (top: ringnorm, bottom: mushroom secondary) and all hyperparameter values for depth 1 (left) and depth 5 (right) CART tree base learners, over 5 seeds.
17

---

Published in Transactions on Machine Learning Research (10/2025)
each method occupies different point along this Pareto front?, highlighting distinct performance-sparsity trade-offs. CG-Boost often lies on the rightmost part of the front, yielding ensembles that perform well but use most of the generated base learners. LP-Boost, QRLP-Boost, ERLP-Boost, and NM-Boost offer an interesting range of tradc-offs, as they are often able to improve sparsity while preserving predictive performance. Overall, we observe that the different lotally corrective approaches are complementary, i.e., they are placed in different parts of the Pareto front, and the selection of the method may be determined based on the specific aceuracy-sparsity tradeoff requirement per dataset.
Observation 13
We observe clear trade-off between accuracy and sporsity, and most methods placed on the Pareto front of both metrics, i.e., they build non-dominaled ensembles.
For depth-5 trees, Figure 7 shows that MD-Boost is often dominated, i.e., there is always a method that finds better accuracy and sparsity. However, its best-performing hyperparamcter typically lics on the frontier, underscoring the importance of careful tuning. In MD-Boost, the hyperparameter C' governs the trade-off between maximizing the first moment and minimizing the second moment of the margin distribution. As also highlighted in Demiriz et al. (2002), LP-Boost is prone to degenerate solutions when the set of weak learners is small. Morcover, it is highly sensitive to its hyperparameter: for high value of C, LP-Boost reverts to hard-margin behavior, reint reint roducing the issues identified in Grove & Schuurmans (1998). These effects are clearly visible in Figure 7 (leftmost points, with trivial accuracy) and are consistent across the other datasets.
Observation 14 Hyperparameter tuning is crucial for some totally corrective boosting approaches particularly MD-Boost and I.P-Boosl- as unsuitable values of their trade-off parameter can lead to poorly performing ensembles.
6.6 Reweighting Behavior
We now consider a post-processing experiment where an ensemble of 100 trees is first generated using Adaboost. Each totally corrective method is then applied in a single shot to reweight this fixed ensemble, i.e., to optimize the base learner weights without generaling new ones. Our goal is to assess whether totally corrective reweighting can yield sparser more accurate ensembles compared to the original heuristic solution. Related work has shown promise in post-processing Adaboost ensembles, see Emine et al. (2025). As previously, this experiment is conducted for tree depths 1, 3, 3, and 10. Figure shows the average performance across all datasets, while Appendix D.5 details all results per dataset.
First, we observe that totally corrective methods can slightly improve the predictive performance of the original Adaboost ensembles, in terms of testing accuracy (particularly when using decision stumps) and in terms of accuracy-sparsity tradeoff. For deeper trees (depth 10), reweighting generally does not allow significant performance improvements. Overall, totally corrective methods appear as viable strategy to thin existing ensembles while keeping up performance, especially for shallow tree ensembles.
Observation 15 Totally corrective methods can be an effective post post-processing strategy to sparsify existing ensembles while preserving -or modestly improving- their predictive performance.
However, the reweighted ensembles consistently underperform compared to those natively generated by the totally corrective methods (Figure 1). This indicates that the strength of totally corrective boosting lies not only in its base learner weight optimization, but also in its ability to iteratively generate informative base learners. The performance gains observed with totally corrective methods result from this joint optimization over both base learner selection and weight assignment.
6.7 Effect of Sonfidence-Ratedr Voting
Following the proposal by Demiriz et al. (2002), we investigate the impact of confidence-rated voting in boosting ensembles. In that setting, each base learner hy no longer outputs a binary label (hy X H
iIn multi-objective optimization, the Pareto front contains non-dominated solutions none improve one objective without. worsening another. Here, an ensemble non-dominated if accuracy or sparsity cannot improve without degrading the other.
18

---

Published in Transactions on Machine Learning Research (10/2025)
Test Accuracy Ensemble Sparsity
Accuracy vs Sparsiy Depth
NMM-Boost
NM.
Adaboost CG-Boost
6,09
*L
Boost
-RRL-BBost
QRLP-Boost
ERLP-Boost
Adabons
Augroge AcouDc
3.7
Teating Acsurery
6.025
.LP-Boost
ERLP-Boost
3.74
3:10
3.7%
1.10
+MD-Boost
MD-Beost
26
Number Columes
Number Columnn Used
Test Accuracy vs Ensemble Sparsity on Depth 5
Tlst Accuracy vs Ensemble Sparsity on Depth 10
118
LP-Boost
boost
GG-
odobosst
110
CG G-Boost
Avcrage Rozting Accurooy
QRLP-Boost
+NM-Boost
LP-Boost
QRLP-Boost MD -o--oost
ERLP-Boost
2,00
3.6X
0,009
ERLP-Boost
MD-Bo9 st
NM-Boost
P6 Average Number of Cokmnn Used
184
Average Number Colames
Figure 8: Reweighting of an existing Adaboost ensemble of 100 trees: average testing accuracy compared to average ensemble sparsity over all datasets for decision trees of depth 1, 3, 5, and 10.
{-1,+1]), but rather a real-valued score (hy : X + [-1,1]) representing its confidence in the prediction. These scores are typically derived from the class proportions in the training examples reaching each leaf during tree construction. Confidence-rated outputs allow for finer-grained voting, where each tree contributes proportionally to (an estimate of) its certainty.
Figure 9 provides a summary of the results using boxplots across datasets. Additional analyses incluuing anytime performance, as well as sparsity accuracy trade-offs on individual datasets are presented in Ap- pendix D.6. In line with the observations of Demiriz et al. (2002), we find no significant improvement in final test performance when using confidence-rated trees as opposed to standard CART trees. However, we do observe that the relative final performance of the methods sometimes slightly changes. For instance, MD- Boost often benefits from confidence--ated outputs, while QRLP-Boost and ERLP-Boost tend to degrade in performance when using confidence-rated decision stumps. This likely stems from the limited capacity of shallow trees to produce meaningful confidence estimates. For deeper trees, these effects diminish. For the remaining methods, performance differences between binary and confidenco-rated voting are negligible. Appendix D.6 further shows that confidence-rrteed outputs do not consistently improve anytime performance. That said, for moderately deep trees (depths 3 and 5), we occasionally observe slightly improved anytime behavior of confidencc-rated trees in the early itcrations, espocially for NM-Boost, QRLP- LP-Boost and ERLP-Boost..
Observation 16 We do not observe a sigrvificatt performance difference when using confidence-rated trees versus normal CART trees.
7 Experiments with Optimal Trees as Base Learners
Thus far, we have relied on the popular CART heuristic algorithm generate decision tree base learners. In this section, we evaluate the impact of replacing CART with optimal decision trees (ODTs) instead,
19

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Bo0SS
MD-Boost
Testing Accuracy improvement Confidence-Raber over IDepth
Tasting Accuracy Improvement Confidence-Rated CART over CART (Depth
104%%
380%
Rebaive Rusing Acuraay AcurooyDffaaa Diferanc
13%
Testing Recurecy Dilleretce
2526
54%
30%
NM4-Boost
QRLPsBooMt
LiMBood
CG-Boest
ERLPdbons
MD-Bocal
NM-Daow!
GRLPdioood
LPdioost
CG
Moool
MB--oooe
Tes Accuracy improvement of Confidence Rated CART over CART (Depth 5)
Testing Accuracy Improvement of Confidence Rated GART CART (Depth 10)
10.%%
15%
Rebative Tisting Accurscy Diference
Texting Aeourery Dillerette
5.%
25%
3.2
68%
6:0%
-25%
-129
-38%
-1.9
104 Boost
GRLFiBoost
LP Booot
C6 Boost
ERLP
ND Bosst
NM Boost
UP
CG Boast
ERLFBoostt Soost
MD Boost
Figure 9: Boxplot showing relative improvement of using confidence-rated CART trees over regular CART trees in the trained ensembles over all datasets, for decision trees of depth 1, 3, 5, and 10, over 5 seeds. For visualization purpose, few extreme outliers were removed.
leveraging recent advances in ODTs learning algorithms. Indeed, in the last years, the scalability of these algorithms has improved, making them a suitable alternative heuristics like CART (van der Linden al., 2025). Examples of these scalable algorithms are LDS-DL8.5 (Kiossou et al., 2022), MurTree (Demirović et al., 2022), and Blossom (Demirović et al., 2023). For broader empirical analysis of ODTs, we refer to van der Linden et al. (2025). We decide to conduct experiments with Blossom, due to its memory efficiency at deeper depths and its native support for sample weighting. Blossom maximizes the training accuracy given the maximum tree depth.
To our knowledge, the only prior study evaluating ensembles with optimal trees is Aglin et al. (2021), who investigate LP-Boost and MD-Boost on limited number of small datasets (up to 958 data points) with trees of depth at most 3. They show that some datasets, optimal trees improve performance, but they might also decrease performance on others. They conclude that the objective of the totally corrective method has a large effect on the performance of optimal decision tree ensembles. Our findings support this conclusion across a broader variely of totally corrective methods and ODT depths.
Figure 10 shows the anytime behavior of NM-Boost, QRLP-Boost, and LP-Boost on the ringnorm dataset. In general, we find that the final test accuracy when using optimal decision trees is often similar to CART trees.
Observation 17 We do not observe any significant or consistent difference in anytime behavior between ODT and CART ensembles.
Figure 11 illustrates the improvement predictive performance (aggregated over all datasots) achieved when using ODTs instead of CART trees in the trained ensembles. The results confirm that the performance gain of ODTs is dataset dependent. These findings refine and extend the observations from Aglin et al.
20

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-BoOst
LP-Boost
thgramm
Figure 10: Anytime behavior of several totally corrective boosting methods on the ringnorm dataset, using base learner decision trees of depth 1, 3, or trained either with CART (full line) or with an optimal algorithm (dashed line), the error bars indicate standard deviation over sceds.
(2021): performance improvements can be observed on specific datasets, but the average effect of using ODTs yields similar results to CART. Detailed per-dataset results that support these conclusions provided in Appendix D.7, together with sparsity-accuracy trade-off summaries, which show that ODT ensembles offer no consistent sparsity advantage nor disadvantage compared to CART-based ensembles.
Observation 18 Across all tree depths and nearly all dalasets, the fonal performance of tolally corrective methods is similar when using optimal decision trees compared to heuristic CART trees.
NM Boost
QRLP-Boost
LP Boast
CG Boost
ERLP Boost
MD ID-Boost
Adaboost
Testina Optimal Trees (Depth
Testing
of Optimal CART (Deoth
Resstvv Tiasing Accurayy Difference
Relerive Tenting Accunery biffeweree
68%
-25%
.50%
-30%
-15%
-20%
-106%
1/4 Soost
GRLF
LP LP-Bosst
CG-Boost
ERLP PRLP-Boost
MD Boost
Adaboost
-280%
MM-doost
ORLP-Boost
LP-Soost
CG-Boost
BRLP-Boost
Boest
Adabeast
Testing Accuracy Improvement Optimal Trees over (Depth
Testing Accuracy Improvement Optimal Trees over (Depth 10)
104%
130%
19%
2.45
Rebiive Tosiing Accurscy Difcrrnncs
Redallove Twalnng Arcuraccy Differetce
25%
NM4Boost
GRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Adaboost
NM--Doott
DRIP-Boost
LP-Boost
CG-boot
ERIP-Boost
MD-Boost
Adboost
Figure 11: Relative improvement of the testing accuracy of boosting approaches when using optimal decision trees CART trees over all datasets, for depth 1, 3, 5, and 10 tree ensembles, over 5 seeds.
21

---

Published in Transactions on Machine Learning Research (10/2025)
We conjecture that optimal decision trees are likely stronger individual predictors with lower bias, but their construction may lead to less diversity across iterations. This reduced diversity may ultimately hinder the ensemble's overall predictive performance, yielding limited improvement potential over CART.
8 Conclusions
In this paper, we conducted an extensive empirical study of totally corrective boosting methods based on column generation. We compared four existing methods, two novel formulations, and three -heearlftheeart heuristic baselines across 20 datasets, varying tree depth and base learners. Our evaluation focused on two key dimensions: testing accuracy and sparsity of the ensemble. We found that totally corrective methods can outperform or match heuristic benchmarks, especially when using shallow trees. With decision stumps the common default in boosting- the proposed NM-Boost and QRLP-Boost achieved the best performance among totally corrective methods, with NM-Boost achieving faate-of-the-are accuracy using significantly fewer trees.
As tree depth increases, heuristic methods such as XGBoost and LightGBM tend to gain an advantage in predictive performance. Nevertheless, totally corrective methods remain competitive and often offer a favorable accuracy-sparsity trade-off. We observed that the best-performing methods are typically those that balance ensemble size with careful margin- based optimization, especially NM-Boost, LP-Boost, and QRLP-Boost. These methods often lic on the Pareto frontier between accuracy and sparsity, achioving high accuracy with compact ensembles.
Our margin analysis revealed that neither minimum margin nor margin variance alone is sufficient explain generalization behavior. QRLP-Boost often yields smooth margin distributions, while NM-Boost promotes focus misclassified datapoints. Yet, both strategies can generalize well, depending on the dataset. We also studied hyperparameter sensitivity and found that while most totally corrective methods are stable under tuning, their performance can be strongly influenced by it. In particular, MD-Boost and LP-Boost can suffer when their hyperparamcters are not well aligned with the dataset.
We further evaluated the reweighting ability of totally corrective methods in a post-processing scenario, where they reassign weights pre-trained Adaboost ensembles. While this procedure can improve sparsity and sometimes accuracy, it does not match the performance of fully-trained totally corrective ensembles. This underscores that the strength of totally corrective approaches lies not just in weight optimization, but also in the dynamic generation of new base learners during training. When replacing CART trees with optimal decision trees, we found that performance may increase depending on the dataset, but often is similar to CART.
Our study has a few limitations. All methods were trained using the same base learners (CART or Blossom) ensure fairness, though this may favor disadvantage certain approaches. Despite extensive hyperparameler tuning, some methods may benefit from even finer calibration. Finally, our conclusions are based on binary classification problems and may not fully transfer to regression, multi-class settings, or real-world applications with different structures.
Future work could explore more flexible formulations that adapt ensemble size to the strength of individ- ual learners, or investigate how different types of base learners (e.g., mixed CART and optimal trees or CART trees of different depths) can be used together. Studying totally corrective methods in regression and multi-class tasks, stopping criteria, and applying these techniques in practical domains are also promising directions. Our reweighting experiments also motivate further research into voting schemes, ensemble thin- ning, and hybrid strategies combining heuristic and lotally corrective learning to achieve both sparsily and performance.
Broader Impact Statement
Some of the datascts used in our experiments (in particular, adult and compas propublica) contain sensitive attributes and are known reflect societal biases. We stress that our use of these datasets is for method- ological benchmarking, with no intention for the trained models to be directly deployed. We caution against
22

---

Published in Transactions on Machine Learning Research (10/2025)
uncritical application of our work and emphasize that any real-world use in sensitive domains should be accompanied by thorough fairness assessments and, where necessary, appropriate mitigation strategies. Finally, we argue that sparse ensembles such as those obtained through linear programming boosting approaches- offer practical advantages for the detection and auditing of potential biases.
Acknowledgments
This work used the Dutch national e-infrastructure with the support of the SURF Cooperative using grant no. EINF-13069. It was also enabled by support provided by Calcul Québec and the Digital Research Alliance of Canada, the SCALE AI Chair in Data-Driven Supply Chains, and the Fonds de recherche du Québec - Nature et technologies (FRQNT) through Team Research Project (327090). We thank Gurobi Optimization for extending our license to support large-scale experiments.
Dost-Publication Changes
After publication, we were notified of an implementation error the Blossom library, used for obtaining opti- mal decision trees (ODTs). Therefore, we ran all experiments with ODTs again and updated the conclusions of Section 7.
References
G. Aglin, S. Nijssen, and Schaus. Assessing Optimal Forests of Decision Trees. 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), pp. 32 39. IEEE Computer Society, 2021.
J. Alcalá Alezlá-Fdez, L. Sánchez, S. García, M.J. del Jesus, J.M. Garrell, J. Otero, C. Romero, Bacardit, V. M. Rívas, J.C. Fernández, and F. Herrera. Keel: a software tool to assess evolutionary algorithms for data mining problems. Soft Compuling, 13(3):307 318, 2009.
J. Alcalá-Fdez, A. Fernández, J. Luengo, J. Derrac, and S. García. Keel data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework. Multiple Valued Log. Soft Comput., 17:255 287, 2011.
V. Aziz, O. Wu, I. Nowak, E.M.T. Hendrix, and J. Kronqvist. On optimizing ensemble models using column generation. Journal of Optimization Theory and Applications, 203(2):1994-1119 2024.
P. Bartlett, Y. Freund, W.S. Lee, and R.E. Schapire. Boosting the margin: new explanation for the effectiveness of voting methods. The Annals of Statistics, 26(5):1651 1686, 1998.
B. Becker and R. Kohavi. Adult. UCI Machine Learning Repository, 1996.
J. Bi, T. Zhang, and K.P. Bennett. Column-generation boosting methods for mixture of kernels. In Pro- ceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '04, pp. 321-520 Association for Computing Machinery, 2004.
C.S. Bojer and J.P. Meldgaard. Kaggle forecasting competitions: An overlooked learning opportunity. International Journal of Forecasting, 37())5587-60: 2021.
V. Borisov, T. Leemann, K. Seßler, J. Haug, M. Pawelczyk, and G. Kasneci. Deep neural networks and tabular data: A survey, IEEE Transactions on Neural Networks and Learning Systems, 35(6):7499-7519, 2024.
L. Breiman. Prediction games and arcing algorithms. Neural Comput., 11(7):1493-1511, 1999.
T. Chen and C. Guestrin. XGBoost: scalable tree boosting system. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16, pp. 794. ACM, 2016.
23

---

Published in Transactions on Machine Learning Research (10/2025)
S. Datta, S. Nag, and S. Das. Boosting with lexicographic programming: Addressing class imbalance without cost tuning. IEFE Transactions on Knowledge ond Dala Engineering, 32(5):883-58) 887,,997 2020.
Demiriz, K.P. Bennett, and J. Shawe-Taylor Linear programming boosting via column generation. Machine Learning, 46(1):225 254, 2002.
E. Demirović, A. Lukina, E. Hebrard, J. Chan, J. Bailey, C. Leckie, K. Ramamohanarao, and P.J. Stuckey, Murtree: Optimal decision troes via dynamic programming and search. Journal of Machine Learning Research, 23(26):1 47, 2022.
E. Demirović, E. Hebrard, and L. Jean. Blossom: anytime algorithm for computing optinal decision trees. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 7533-777 7562. PMLR, 2023.
F. Ding, M. Hardt, J. Miller, and L. Schmidt. Retiring adult: new datasets for fair machine learning. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21. Curran Associates Inc., 2024.
Emine, A. Forel, Malek, and T. Vidal. Free lunch the forest: Functionalll--denttieal pruning of boosted tree ensembles. Proceedings of the AAAT Conference on Artificial Intelligence, 39(16):16485 (448):66488116495,, 2025.
C. Feng, A. Sutherland, S. King, S. Muggleton, and R. Henery. Statlog project, 1993.
Y. Freund and R. E. Schapire. Experiments with new boosting algorithm. In Proceedings of the Thir- teenth International Conference on International Conference on Machine Learning, 1CML'96 '96, pp. 148 156. Morgan Kaufmann Publishers Inc., 1996.
Y. Freund and R.E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119 139, 1997.
W. Gao and Z. Zhou. On the doubt about margin explanation of boosting, Artificial Intelligence, 203:1 18, 2013.
A.J. Grove and D. Schuurmans. Boosting in the limit: maximizing the margin of learned ensembles. Proceedings of the Fifteenth Aatiooall/Tentee Conference on Artificial Intelligence/ Dreeligence/nnoovatiie IInoovatiee Applications of Artificial Intelligence, AAAI 198/TAAI '98, pp. 692 092-699, USA, 1998. American Association for Artificial Intelligence.
T. Hastie, Rosset, Zhu, and H. Zou. Multi-class adaboost. Statistics and its Interface, 2(3):349 360, 2009.
C. Hinrichs, V. Singh, L. Mukherjee, G. Xu, M.K. Chung, and S.C. Johnson. Spatially augmented LPboosting for AD classification with evaluations on the ADNI dataset. Newrolmage, 48(1):138 149,, 2009.
H. Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994.
G. James, D. Witten, T. Hastie, and R. Tibshirani. An Introduction to Statistical Learning: with Applications in R. Springer, 2013.
A. Janosi, W. Steinbrunn, M. Pfisterer, and R. Detrano. Heart Disease. UCI Machine Learning Repository, 1989.
G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q, Ye, and T. Liu. LightGBM: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
M. Kelly, R. Longjohn, and K. Nottingham. The UCI machine learning repository, 2025.
H.S. Kiossou, P. Schaus, S. Nijssen, and V.R. Houndji. Time constrained DL8.5 using limited discrepancy search. In ECML/PKDD (5), 2022.
24

---

Published in Transactions on Machine Learning Research (10/2025)
S. Makridakis, E. Spiliotis, and V. Assimakopoulos. M5 accuracy competition: Results, findings, and con- clusions. International Journal of Forecasting, (5(4):1346-1364 2022. Special Issue: M5 competition.
S. Makridakis, E. Spiliotis, R. Hollyman, F. Petropoulos, N. Swanson, and A. Gaba. The M6 forecasting competition: Bridging the gap between forecasting and investment decisions. International Journal of Forecasting, 2024.
R. Mitsuboshi, K. Hatano, and E. Takimoto. Boosting as Frank- Wolfe. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop), 2022.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825 2830, 2011.
R. Quinlan. Thyroid Disease. UCT Machine Learning Repository, 1986.
C.E. Rasmussen, R.M. Neal, G. Hinton, D. van Camp, M. Revow, Z. Ghahramani, R. Kustra, and R. Tib- shirani. DELVE: Data for evaluating learning in valid experiments, 1996.
G. Rätsch, T. Onoda, and K.R. Müller. Soft margins for AdaBoost. Machine Learning, 42(3):287-33) 320, 2001.
G. Rätsch, M.K. Warmuth, and K.A. Glocer. Boosting algorithms for maximizing the soft margin. In Advances in Newral Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
J. Roy, M. Marchand, and F. Laviolette. A column generation bound minimization approach with PAC- Bayesian generalization guarantees. In Proceedings of the 19th International Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Rescarch, pp. 1241-1249. PMLR, 2016.
C. Shen and H. Li. On the dual formulation of boosting algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32:2216 1-2216-2231, 2009.
C. Shen and H. Li. Boosting through optimization of margin distributions. IEEE Transactions on Newral Networks, 21:659 666, 2010.
C. Shen, H. Li, and A. van den Hengel. Fully corrective boosting with arbitrary loss and regularization. Newral Networks, 48:44-58, 2013.
P. Turney, Pima Indians diabetes data set, 1990.
E. Uchoa, A. Pessoa, and L. Moreno. Optimizing with Column Generation: Advanced branch-eut-and- price algorithms (Part 1). Technical Report L-2024-3, Cadernos do LOGIS-UFF, Universidade Federal Fluminense, Engenharia de Produção, 2024.
J.G.M. van der Linden, D. Vos, M.M. de Weerdt, S. Verwer, and E. Demirović. Optimal or greedy decision (rees? revisiting their objectives, luning, and performance, 2025. arXiv preprint.
D. Wagner, D. Heider, and G. Hattab. Secondary Mushroom. UCI Machine Learning Repository, 2021.
M.K. Warmuth, J. Liso, and G. Rätsch. Totally corrective boosting algorithms that maximize the margin. In Proceedings of the 23rd International Conference on Machine Learning, ICML '06, pp. 1001 1008. Association for Computing Machinery, 2006.
M.K. Warmuth, K.A. Glocer, and S.V.N. Vishwanathan. Entropy regularized LPBoost. In Algorithmic Learning Theory, pp. 256 271. Springer Berlin Heidelberg, 2008.
S. Zhai, T. Xia, M. Tan, and S. Wang. Direct 0-1 loss minimization and margin maximization with boosting,
In Aduances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
M. Zwitter and M. Soklic. Breast Cancer. UCI Machine Learning Repository, 1988.
25

---

Published in Transactions on Machine Learning Research (10/2025)
A
Datasets
In this section, we provide more details about the datasets used. We study 13 datasets commonly used in related works (Bi el al., 2004; Rätsch el al., 2007; Warmuth et al., 2008; Shen & Li, 2010; Mitsuboshi el al., 2022) which were proposed as binary classification benchmark by Rätsch et al. (2001) and originally sourced from UCI (Kelly et al., 2025), DELVE (Rasmussen et al., 1996) and STAT-LOG (Feng et al., 1993). We retrieved some datasets from the KEEL repository (Alcalá-Rdez et al., 2009; 2011). Some of the challenges were transformed from multi-class to binary classification by Rätsch al. (2001). Given that many of these datasets are synthetic, we decided to supplement them with seven well-known and publicly available real- world datasets. Table 3 summarizes the key statistics of the benchmark datasets and the supplementary datasets, after preprocessing.
All features are binarized as this streamlines presentation and comparison of models, and it also allows us to conduct experiments with optimal decision trees, whose state-of-the-art learning methods require binary features. Features are separated into numerical and categorical types. Numerical features are discretized into four equal-sized bins and transformed via one-hot encoding, producing binary indicators for each bin. Categorical features are one-hot encoded with the first calegory dropped. In some cases, binarization leads to large number of features. To reduce computational effort, we therefore conduct feature selection if needed. Features are ranked by their contribution to reducing impurity in random forest model, and subsets of features are iteratively evaluated for validation accuracy using a forward stepwise selection approach. The subset is selected as the smallest feature set that maximizes predictive performance, see James et al. (2013). Below, we explicitly indicate when we did feature selection.
Banana is an artificial dataset where instances belong two clusters with a banana shape. There are two features corresponding to the and y axis, respectively. See https://sci2s .ur.2.s...r...... ugr es/keee//ataaeee php? cod=182 for the data repository.
Breast cancer is a dataset sourced from the University Medical Centre, Institute of Oncology in Ljubljana (Slovenia) (Zwitter & Soklic, 1988). The challenge is to forecast recurrence events for patients with breast cancer stages I to I11, see https: /ttp://///oooog/1..... 24432/2C11PP C5114M
Diabetes is a dataset from the National Institute of Diabetes and Digestive and Kidney Disease for which we need to predict- based diagnostic measurements- whether patient has diabetes (Turney, 1990). All patients here are females at least 21 years old of Pima Indian heritage, see https://10.0. 68. 224/ 7zcc8v6hvp.1.
A solar flare is a sudden burst of energy and radiation from the sun. The data contains observations of solar activity, specifically focusing on sunspots and solar flares, and the challenge is to prodict the occurrence of a lype of solar flare, see http:// //xxxdx.iii .ar.lorr...... 2erg/10.521//1 w0w.552220oo... 18110.
German credit is a dataset of customers who take a credit from a bank. Each customer is classified having good or bad credit risks according to set of customer attributes (Hofmann, 1994), see https: //doi
//doi.org/10. org/10. 24432/C5NC77.
Image is a dataset with the task to determine the type of surface of each region in an image. The instances are drawn randomly from a database of 7 outdoor images. The images were hand-sogmented to create a classification for every pixel. Each instance is x 3 region, see https://doi. /t//d/i..ggg///////// org/10 100 24432/C5GP4N.
The heart dataset has as challenge to predict heart disease in patients, it is a combined set from four locations: Cleveland, Hungary, Switzerland, and Long Beach VA (Janosi et al., 1989), see https://dof org/10 1...22433//C2P4..
The ringnorm dataset is an artificial binary classification dataset. The challenge is to classify two 20- dimensional Gaussian distributions with (0 41) and ((a, I), with = (a, a a......). and a = 1/v20, see http://dx /wo./xxxoooo...o doi.
18110.
The problem posed in the splice dataset to recognize the boundaries between exons (the parts of DNA sequence retained after splicing) and introns (the parts of the DNA sequence that are spliced out). Splicing
26

---

Published in Transactions on Machine Learning Research (10/2025)
is the removal of superfluous points on DNA sequence during protein creation. We reduced the number of binarized features from 240 to 61, see https://doi. wttg/....433///5M....... 24432/C5M888.
The task in the thyroid dataset is to detect if a given patient is healthy or suffers from hypothyroidism. The data is originally sourced from the Garavan Institute in Sydney, Australia (Quinlan, 1986), see https: / //doi. . org/10. 10. 24432/C5D010.
The task for the titanic dataset is to predict if passenger survived the Titanic shipwreck based on passenger attributes. We did not use the benchmark version by Rätsch et al. (2001), this contains only 24 data points, and used the version publicly available with 887 data points, see http://dx: /ttp://xx.do.... wtwp..do..oogg......11 5281/ zenodo. 18110. We reduced the number of binarized features from 333 to 94.
The twonorm dataset is an artificial binary classification dataset. The challenge is to classify two 20- dimensional Gaussian distributions with means (a, a, .......)) .)) and --a,-a,..... aa) and 2/v20, see http: //dx. dolx.doi.oo orgg//00.
10. 5281/2enodo. 18110.
Waveform is artificial binary classification dataset of waveform data, with each sample containing 40 attributes, with added noise. Each class is a random convex combination of two of the waveforms, see http://dx. http//xxxxoo... orgg 10. 520.22/ezeooo.. 111100 18110.
Below, we describe the datasets that are not part of the benchmark by Rätsch et al. (2001), but were selected by us as a supplementary challenge.
Adult is well-known classification dataset for predicting whether annual income of an individual exceeds $50K per year based on census data (Becker & Kohavi, 1996), see https://doi. org/o0..//.. 10. 24432//5XX20.. The dataset is studied in many related binary classification studies, among others in Demiriz et al. (2002) and Zhai et al. (2013).
Furthermore, we utilize the folktables library to construct four additional datasets based on census data. This library was constructed to address limitations of the adult dataset, such as outdated feature encodings and overly specific or unrepresentative target thresholds. We use two standardized challenges, see Ding et al. (2024): (i) predict whether low-income individual, not eligible for Medicare, has coverage from public health insurance (public coverage), and (ii) predict whether study both challenges in two states, California (CA) and Texas (TX), which exhibit significantly different population characteristics in terms of demographics, income distributions, and socio-economic diversity. For both challenges, we randomly sampled 25% of the 2018 data to keep the dataset size manageable. For the public coverage datasets, we left out redundant features and reduced from 622 to 57 (California) and from 591 to 130 (Texas). Datasets can be retrieved via the folktables Python library, using the specific challenges as mentioned in Ding al. (2024).
adult is employed (employment). We
Compas (Correctional Offender Management Profiling for Alternative Sanctions) is dataset for which we need to predict criminal defendant's likelihood of reoffending in Broward County, Florida, see https: //www.kaggla features.
We preprocessed the data such that we remain with 14
Finally, we include secondary mushroom, a dataset of simulated mushrooms for binary classification into odible and poisonous. Compared to the primary mushroom datasct, this simulated data contains 7.5x more examples, which helps to study scalability of algorithms to larger datasets (Wagner et. al., 2021), see attps://doi.org 24430///522232/55550000 We reduced the number of binarized features from 111 to 63.
27

---

Published in Transactions on Machine Learning Research (10/2025)
Table Summary of the datasets
Dataset
Features
Data Points
Class distribution
banana
5300
55.1%
breast cancer
36
263
72.6%
diabetes
112
768
65.1%
german credit
80
1000
72.1%
Benchmarks
heart
52
270
57.4%
image
72
2086
55.0%
ringnorm
80
7400
50.9%
solar flare
36
144
57.6%
splice
61
2991
55.0%
Uhyroid
215
70.2%
titanic
94
887
61.4%
twonorm
80
7400
50.7%
waveform
84
5000
66.6%
adult
19
48,842
76.1%
Supplementary
compas
14
7206
54.9%
employment CA2018
84
75,660
57.3%
employment TX2018
84
52,089
58.0%
public coverage CA2018
57
34,638
63.2%
public coverage TX2018
130
24,732
81.2%
secondary mushroom
63
61,069
55.2%
B Formulations
In this section, we provide the mathematical programming formulations of the benchnarked LP-based boost- ing techniques. In most cases, except for QRLP-Boost and ERLP-Boose we solve the primal formulation because these are often simpler in terms of variables and constraints than their dual counterpart and there- fore, faster to solve, as shown in Shen et al. (2013). Nonetheless, we provide both the primal and dual formulations for most methods.
Table 4: Notation overview for primal formulations.
Primal notation
Meaning
features for data point. label for data point i base learner j. part of the H
yi
hy
Wy
weight. for each base learner hy in the ensemble margin for data point
Pi
&
slack variable for each data point number of data points in the training set
M
T
number of base learners in H regularization hyperparameter
C
We adapt and unily the notation from the original papers to match the one introduced in Section 2. The notation used for the primal formulations summarized Table 4. For the duals, we use the variable u, denote the sample weights, ie., score provided to each data point in the dataset that indicates misclassification or distance to the decision boundary for the current ensemble (and is usually used weight the examples when fitting new base learner).
28

---

Published in Transactions on Machine Learning Research (10/2025)
B.1 LP-Boost
LP-Boost is proposed in Demiriz al. (2002). The tradeoff hyperparameter is tuned balance be- tween misclassification error and margin maximization. In Demiriz al. (2002), multiple alternative but equivalent formulations are provided; found the following formulation to be the most robust in terms of hyperparameter sensitivity, The LP-Boost primal problem is formulated as:
T
M
minimizow.
Σ
w
+ +CC
Σ
C3
(18)
==1
1=1
T
subject to
Σ
Wi (x;) + 21,
Vi I.......,MM M,
(19)
j=1
W 2 0, Vj = ,,..., T,
(20)
&: 2 0, Vi = 1 1,..., M.
(21)
The corresponding dual formulation is:
M
maximize,
U;
(22)
M
subject to
Σ
U; Yo (2;) 1 Vj = ::=....... T, I,
(23)
i=1
0 C,
== 1 L.....
(24)
B.2 CG-Boost
CG-Boost is a quadratic program proposed in Bi et al. (2004). Just in LP-Boost, C is tuned to balance misclassification error and margin maximization, but Boost regularizes the weights w with the L2 norm instead of the L norm.
T
M
minimizew..
w
+
&
(25)
subject
y6
Σ
Wi (x;) + & 1,
Vi= ......M,
(26)
j=1
Vj T...,T. 220, 0, Vi= 1 1,..,,M. M.
"i 2 0,
(27)
(28)
For the corresponding dual, the primal variable w remains the dual:
maximize, minimize
U4
2
(29)
j=1
subject to
Ui Wi b (x,) S whi Vj = I.....
(30)
0 05usc
(31)
29

---

Published in Transactions on Machine Learning Research (10/2025)
B.3 ERLP-Boost
A line of research has focused on developing alternative LP-Boost formulations with proven iteration bounds. Total-Boost (Warmuth et al., 2006) and Soft-Boost (Rätsch et al., 2007) have, in contrast to LP-Boost, an iteration bound, of O : In M) itcrations to produce a linear combination of base learners for which the soft margin is within e of the maximum minimum soft margin. Total-Boost and Soft-Boost only differ in the capping parameter, as Total-Boos Boottt uses C 1, whereas Soft-Roost has C' E [1,
As mentioned in Section 3, ERLP-Boost (Warmuth al., 2008) performs similarly to LP-Boost and Soft- Boost overall but offers theoretical bound on the number of iterations and typically achieves faster reduction in error than Soft-Boost during the early stages of training. In E.R.P-Boost, the hyperparameter C balances the tradeoff between entropy regularization and the original LP-Boost objective (the worst-case margin), by constraining the maximum weight assigned to each example in the distribution.
We solve the following convex programming dual in an iterative fashion, i.c., we solve and obtain a new distribution in each iteration until convergence. This makes ERLP-Boost potentially slower in terms of computational time per generaled base learner.
minimize..g
Ee A(,,u))
(32)
17
subject to
Σ uey:hy((0))
Vj = 1, ,,.... T. S Ecs
(33)
M
Ui = 1,
(34)
i=1
us 1 C'
Vi = 1, ,,...,M. M.
(35)
Here, 17 is a small constant calculated by:
M 0.5,
max
Lestop
(36)
with stop a small constant also used to set the maximum number of ilerations and the convergence criterion:
8
Maximum iterations max <stop/2 /2' (estop /2)
(37)
We obtain the relative entropy term A(u", u) as follows:
Σ
log(u +c) +
Ui ui u
(38)
which is the first order expanded KT-ddivegence with small perturbation u to prevent issues zero. Note that we obtain the weights wj as the dual values of the soft margin constraint after convergence or the maximum number of iterations are reached.
B.4 MD-Boost
MD-Boost is proposed in Shen & Li (2010) and focuses on the distribution of margins. Here, the tradcoff hyperparameter C. balances the normalized average margin and the normalized margin variance, i.e., the first and second moments of the margin distribution, respectively. The matrix MMM is given by:
A
M
(39)
M
M
30

---

Published in Transactions on Machine Learning Research (10/2025)
The calculations with A can place large computational burden when the number of data points M is large. As suggested in Shen & Li (2010), we can approximate A by its identity matrix. In line with the original work, we decided to use this approximation for all datasets, as we observed no performance decrease but a significant speedup.
M Ap
maximizew..
Σ
Pi
2
(40)
i=1
subject to
Pi Vi
Wj hz( vi= M,
(41)
T
Σ Wi = C
Yj = I..... T
(42)
==1
W/ 2 0, fj 1, I.......
(43)
The dual formulation is given by:
minimizerg
r (u 1) A- (u- -
(44)
2C
M
subject to
Vj = I....,T U ST.
(45)
Note that the dual variable is unbounded and is no longer distribution, see Shen & Li (2010).
C Hyperparameters
Hyperparameter tuning is conducted as follows. We split the dataset into a 60% training set, 20% validation set, and 20% lest set. We perform 5-fold cross-validation for each datasel and method, evaluating 10 hyperparameter values uniformly spaced within the ranges shown in Table 5. This way, we ensure that each method has similar opportunity to find good models. We select the best hyperparameter based on the validation set performance, and report statistics on the test set.
Note that, except for ERLP-BBost and QRIP-Boost, each totally corrective method has only single hyperparameter. For both ERLP-Boost and QRLP-Boost, decided to only tune the trade-off parameter C' between relative entropy and the maximum edge, and set to 0.01, as this is also done this way in the original ERLP-Boost paper, see Warmuth et al. (2008). For MD-Boost, we decided to use the Moore-Penrose pscudo inverse approximation of the matrix A, as this did not yicld an observable performance decrease and does decrease computational time significantly.
For the Adaboost, XGBoost, and LightGBM benchmarks, we solely tune the learning rate.
D Complementary Results
In this section, we provide detailed and complementary results. First, in Section D.1, we report computational times per dataset and method, and in Section D.2, report the global performances (testing accuracy and sparsity) of all studied boosting approaches across all considered datasets, for depths-3 and depth-10 CART decision tree base learners, respectively. We display in Scction D.3 the anytime predictive performance of the different benchmarked methods on the adull dataset. Afterward, in Section D.4, we show the performance across hyperparameter values for all datasets. Next, we provide the detailed results for the reweighting of Adaboost ensembles experiment in Scction D.5. We display the complete results for the confidenco-ratod voting experiment in Section D.6, and finally, we provide the full results for the optimal decision trees experiments in Section D.7.
31

---

Published in Transactions on Machine Learning Research (10/2025)
Table 5: Hyperparameter ranges used for each method (applied consistently across datasets).
Method
Hyperparameter range
NM-Boost.
(10 10-0.333
QRLP-
(1....)..06MM)
LP-Boost
"10" 0.33.333
CG-Boost
{10 10 100,11000000 0.33)
ERLP-Boost
1....,,.066,TT
MD-Boost
(l...., 120}
Adaboost
(10-3
XGBoost
{10
LightGBM
{10 {10-3.....
D.1 Computational Time
Table 6 shows the total CPU time for obtaining ensemble of CART trees for each dataset and method. We only report results for depth-1 base learners as do not observe a significant difference in CPU times between different depths. Note that this was expected, since considering more complex base learners does not increase the search space (number of variables and their domains) of the optimization problems underlying totally corrective formulations (it only affects the base learners' building, which is negligible using CART trees). Note that we disabled early stopping for all totally corrective methods to allow each to construct ensembles with the same number of base learners. Therefore, CPU times could be significantly reduced, as in most, cases the totally corrective methods converged before 100 ilerations, see, for instance, Figures and 3.
As expected, the heuristic methods require only fraction of the time compared to the totally corrective methods to train. For the smaller datasets (< 1000 examples) the training time is less than minute, but the larger datasets require significantly more time. Nevertheless, even for the largest datasets (with up to 75,660 examples and 130 features, as detailed in Table 3), the running times remain practically reasonable, especially given the observed improvement in the accuracy accuracy/sparsitg trade-off (as summarized Figure 1).
Table 6: Computational times in seconds for different boosting methods using CART trees of depth 1, averaged over five seeds. The last row shows the mean and median CPU time in seconds.
NM-Boost CPU time
QRoF-Booet CPU time
LP-Boost
CG-Boost
ERLP-Boust
MD-Booet CPU time
Adaboust
XGBoost CPU time
LightGBM
Dataset
CPU time
CPU time
CPU time
CPU time
CPU time
banana
434.5 + 2.1
235.8 1.0
425.3 + 244
433.4 20
166.2 = 133
436.1 39
0.2 + 0.0
022 + 0.
0.0 0.0
becast, Deneer
21.3 0.3
130 + 0.3
21.7 +17+00 0.4
22.3 + 0.1
9.2 + 0.3
22.4 + 0.2
0.1 + 0.0
0.2 + 0.0
0.0 0.0
diabetes
0.5
37.0 0.3
634 0.7
6633 4: 0.7
24.3 0.4
63.3 4:
0.2 12:100 0.0
4:
0.0 0.0
german
heart
0.3
13.5
22.5 1
23.2 0.3
23.0 4
0.1 0.0
0.2 1
0,0 0.0
Imsage
173.5 1.0
95.8 0.5
100.3 à: 0.7
172. 1.8
62. 0.5
101.4 +: 83.5
0.2 0.0
0.2 4 0.
ILD 0.0
ringnorm
6404 + 6.0
345.2 + 2.2
6206 + 5.0
G11.6 2.5
216.2 = 2.4
G10.2 3.9
0.5 0.0
0.2 + 0.0
0.0 0.0
12.5
7.6 0.3
12.2
12.6
12.5 +
+ 0.0
0.0
splice
2.4
1.0
1.7
24022
243.8 2.
0.3
thyroid
1833
0.0
titanic
73.5 + 0.6
42.3 0.2
71.5 0.4
76.5 + 0.8
27.3 + 0.5
76.1 +
0.2 0.0
0.2 +
0.0 0.0
twonorm
646.3 + 3.8
543.1 1.5
618.3 4.8
611.7 4.1
217.4 + 1.2
613.3 4:
0.5 0.0
0.2 + 0.0
0.0 4: 0.0
waveforrn
433.1 1. 2.6
231.5 2.0
608.6 1. 3.2
410.1 3.8
148.2 1 0.7
409.6 2.3
0.4 1.00
1
0.0 0.0
2220.2
2618.7
compas
188.4 3.2
5e60.9
Sett.4 6.0
0.2
010
employment CA2018
2618.4 19.5
2016. 118.4
2407.1 15.0
2570.0 8.1
2273.2 13.3
2363.G 17.6
2.6 2 0.0
0.7 + 0.
0.3 0.0
amplayment TX2018
2614.3 + 135.1
2413.0 + 34.2
2548.1 + 9.1
2507.8
27.7
1062.1 + 12.8
2406.8
26.7
1.8 0.0
0.7 + 0.2
0.2 0.0
public coverage CA2018
2527 5
1594.0
2612.0
96.2
2617.7 10.7
1083.4
7.0
2961.9 +:
1.1.0.011
4
0.1 0.0
public coverage TX2018
1125
mushrom secondary
2451.2
116.2 2581.5
2599.1 127.5
2586.1
16.4
1835.9
16.9
2589.6 17.8
2.1 1. 0.3
0.5 1.
0.2 0.0
Monn/ Median
911.5/433..8
716.7/233.7
012.2/417.0
508.0/441.8
510.6/152.2
906.2/422.9
0.7/0.2
0,3/0.2
0.1/000
32

---

Published in Transactions on Machine Learning Research (10/2025)
D.2 Securacy-Sparsity Performances
We report in Tables 7 and 8 the global performances (testing accuracy and sparsity) of the different totally corrective boosting methods and benchmarked heuristics, for all considered datasets, for depths-3 and depth- 10 CART decision tree base learners, respectively. They complement the average results and the per-dataset results for depths-1 and depth-5 CART decision tree base learners provided and discussed in Section 6.1.
As can be observed in Table 8, Adaboost stopped after one iteration on the heart datasct with depth-10 trees due to perfect training accuracy. While this results in a particularly sparse and interpretable model (i.e., a single decision tree), we note that including additional trees enhances generalization -as for this experiment, the other boosting approaches all reach better testing accuracies than Adaboost.
Table 7: Testing accuracy and number of non-zero weights for different boosting methods using CART trees of depth 3, averaged over five seeds. Bold highlights the best accuracy among all methods, while a star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
quta
KICLP
Xilleed
baeaza
0478 1111
11
3670 MLL
77
ESD 885
11
1X
8.70 1001
L,00 8001
35
4.21
E05
3M
8,52 1855
3M
666S 3016
0.37 1.00
3631
6A921100 1815
1M
1.01
3366 1101
1.014 1354
1-21 1027
18
5.00 3015
1000 à 1135
0923 1.2
36
35
18
1.01 1181
35
1-00-1100 2107
16
1001 01.4
1011
16
Sace
360 300
5.6 1/55
18
6:02 1181
1385 116)
100" 2107
101
5 1100
8.024 5180
16
1080
11011 1100
15
1191
1090 1091
EWIT 11.5
31
1301 8.00
1.6 1160
18
1061 1091
1700 100
183
LMI 1:84
92
LK7 A1
2661
22
1.50
1:81
16
1100
183
DAT) 1.00
1315
105
1900 1311
136-2 1017
1054
crnpberne CABRIA
0118 030
AT3P-9 1061
19
1387
11
1710 1107
15
175-110
11
176:91007
18
6/744 3301
1755 1181
75301
1700
1
6311
4751
eammir Th
1300
1.61
1:77
1.11
0.63
1401 1000
053--080
196 1101
1.0 1000
10:-10
198 100
Mane Medike 3607 00860'
16700
196086
03/8
M.000
41//15
21.00
18:94
13000
19/000
Table 8: Testing accuracy and number of non-zero weights for different boosting methods using CART trees of depth 10, averaged over five seeds. Bold highlights the best accuracy among all methods, while a star* marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
N3L-Baan
SPoBeen
CG Bast
SChook
Datiet
Are.
Cdd.
Ast.
Cik
Asc.
Cok.
Asc
Cok.
Alc.
Cak
Alc.
Cdl
A6G
Cile
Asc.
Cub.
Asc
Clk.
1447 1.4
1100
1.81
36
1015 1112
1038 1127
1463 1114
US08 $1.5
131
6.38 1181
6114
13
JB
0108
$182
13)
4
14
0852 0134
18
0851
1088
0855
131
11K
1.36
00X
CSTE
EXI
0515 1.00
1001
201
035
058
058
1200 1.30
0562
0.00 1965
0347 2100
068 032
031 1355
2135
1M
052 100
35667 000
0064 1000
114
190
E E085
14
0315
039
wenderm
1.80
0086
ET57 1130
0/00
0523
186
190
0008 1001
14
IOoppesRE CASHS
L1K
(338
L752
6797
62561181
segpogmen 13208
6352 1.8
0755 030
626 0 6.00
6531 01/0
632 020
L70 1.06
3.79.115 1.00
130
6.6
16
pubdi owntage CA2G3
L1K)
116
03211 1..5
1391
0011
1717
rocuadayy
1130
1130
1100
10901100
(366
1.99
1000
0208/2201
D.3 Anytime Performance
We report in Figure 12 the lesting accuracy of the different considered boosting approaches al each performed iteration during the ensemble training, for the adult dataset. This complements the results provided in Scction 6.2 for the image and ringnorm datasots. Consistent with our previous observations, we note that the anytime performance of methods is especially different in early iterations, but gets close together for all methods later.
33

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
LP-Boost
Adaboost
XGBoost
lightGBM
Depth 1 on soult
Depth on adult
0.6
6.0
6,0-
Tasting Accuracy
Texting Acturncy
120
leraaions
Dopth on aoult
Dopth 10 adult
Testing Accrscc
Twxiting Accuracy
075
6.00
6:14
Herations
Retwiions
Figure 12: Anytime behavior on the adult dataset for selected methods (all other methods in gray), for CART decision trees of depth 1, 5, and 10. Error bars indicate the standard deviation over 5 seeds.
D.4 Hyperparameter Sensitivity
Figure 13 displays the tradc-offs between testing accuracy and number used columns (i.c., base Iearners). for the considered totally corrective boosting methods, for depth-1 decision trees, over all tested datasets and all hyperparameter values. This complements the results presented in Section 6.5 for two datasets and depth-1 and depth-5 trees.
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Depth 1 Teesinng Accuracy Number of Columns (Al Hyperpaareeeees and Data sets)
Depth Testing Accuracy vs Number of Columns (All Hyperparameterss and Data sets)
Torting Arcuney
Accuracy
Number of Columes Used
Number of Columns Used
Figure Average testing accuracy compared to average ensemble sparsity over all datasets and all hyperparameter values for depth trees, over seeds. The methods are split over two columns for visualization purposes.
34

---

Published in Transactions on Machine Learning Research (10/2025)
D.5 Reweighting Behavior
We provide the per-dataset results of our reweighting experiments in Tables 9, 10, 11, and 12, for trees of depth 1, 3, 5, and 10, respectively. This complements the aggregate results provided in Section 6.6.
Table 9: Testing accuracy and number of non-zero weights for different boosting methods for a reweighting experiment using 100 depth 1 trees generated by Adaboost. star* marks the best among lotally corrective methods. The last row shows mean and median for both statisties. Adaboost hyperparameters were not tuned for the reweighting experiment.
NML Porst
QRIP. P.
MrB.Boot
Adshoret
Datint
Ant
Cols
Anc.
Cola
Ace.
Oob.
Are.
Cola
Are.
Cids.
Art:
CMds.
Anc.
Cida.
0,790
persen
0.77
Iusge
EN38 2
OAIE
EAS 2
0,97
IUSI E
rigmerm
ILSN EURE
miker Hare
CUR8
<plle
E044
CUNI
TUNS DJ06
4.0035
0.34 0.305
0U32 EVIDD
Eagrold
EONR à
EURE
6041
TURS SUNO
IUND E484
Ehankc
L:34
0,792
IURI EURS
E/MC BX00
E.GE" 0.92
0.355 0.00
0.335 00221
soveforn
0887 t/0E
TUSK& DU06
32
4.0535
0.5% 0.113
(UNS) CUIn
330
adat
1338 1UN
TUSTA
1000
KAES DUNG
0,133 0U305
IURIS EURN
ranqus peopiiliia
1465 1.09
0403
DO00 0012
890 0002
130
0429 DI0T
0/022 888
0:570 C006
rmplytoon CASmA
6/84 4.03
B782" 0.30
IUTS 1000
0090
130
6.26 D000
0.333 00305
0,75 CURM
implimmen TX300a
6.764 3.63
625 à 8.00
(.264 à 0000
0.366 0.00
CTPP à 0.353
0.113 0.39
0.731 C/00
330
publi: coneagg CABUE4
03222
(U00 8: 1986
0.590 1000
331
0.99 0008
LU96 DURN
130
publi comeage TK2044
0100
0an + 8000
1U5S + 1006
0.555 0000
130
0.30 (100
79
130
musimmm sncmiooy
021T 6000
(1796
0000
0701 0:00
0/230 0008
Menn/Mellus
16
1026
(k)
19792
0.39 "0.000"
19.1/ 21.
(1.79 19.7
6/99
Table 10: Testing accuracy and number of non-zero weights for different boosting methods for a reweighting experiment using 100 depth 3 trees generated by Adaboost. A star" marks the best among lotally corrective methods. The last row shows the mean and median for both statistics. AAdabosst hyperparameters were not tuned for the reweight experiment.
Datinst
Are:
Cida.
Acc:
Cola
Acc.
Calo
Gabs
Are.
Cola.
Azc.
Cabs
Cids.
D4B0 +0
EUTS -001
100
0450
EXT0" -0014
0.625 0136
Ioreet COuRT
8933 1000
(L93) 102T
E503" 6610
100
(L312
0333-100 (33
dabetos
0.022 03230
0,751 C/06
67.3 1/02
100
0/334
0.52
0.55 0.25
gresnn roalis
0555 0025
0.5W 100B
100
0191 012
0155= 01/0
boot
0/007 +.3.2
0:41 0006
0.92 0085
0:80 1166
100
0876
0.25
0,62 0163
015 -032
Image
0339 000
633 6006
096--100
100
0311 -0007
0141 -030
ragera
0096 +.33
6510 0091
E/PP 0.85
ESS1 000C
100
0531 0.901
0.865 0.300
aoher Hare
0820 1080)
0355 1000
31
Dag 2 11800
USS 1184
D00
0179 0290
USS 2 6303
34
0.822 0377
109
syloo
IUMP 1.300
56
0.79 0007
199
00S 1168
100
0199 0197
330
030 2 616
100)
0.503 0.36
109
Diyrad
0915 0ipe
0510 0028
6332
0900
100
E005"
0141-100 03327
Ctank
0330 001
batr 255
90
0.90 6007
0300 1007
100
0338
028
0.82 01700
1000
0333 C0KE
100
0100 0039
mondomn
US5 = 1014
48
0155 2 UUK
20
0,92 1004
Eass" = 100
100
0155
2 118
10T2 2 0307
0.332 1030
109
adelt
0812 tike
0812 00001
198
0.11 1006
OSEE
100
0505 0101
330
02000 0165
(10)
0331 0090
ranqas perpoblicn
0811- onte
0363 0017
D026- 0.15
EAAA" 00t6
100
0483 0.15
0.04 5007
01664 0011
0338 D00
07786
0728
100
623.4
0711-000 0330
emplynmnn IXasas
4736 tuke
30
MGAA 2 9.00
26
IL72 = 1UR
MZ2 2104
D00
WENT 2 0.002
UTB- 2 0368
100
publte coneegge CazEBe
2 1131
31
10300 UUK
10
uaW 1164
100
0787 5 01005
U33 2 016
0100 1.94
100
puble consego TX3008
0551
0351 0/00
07
0.501 1900
0000 1160
100
03077
0.003
0A0 2 6162
17
0M8 0.90
109
masimam occandory
0007
0185 0000
6703
E103"
100
0130
0115
01854 00114
Moen/ Medien
08511 1337
290/ 28.
1908 10841"
1001
(U88) 1050
51. 0331/10611
(111 1919
0286 1041
US51 (13543
(00
D.6 Effect of Confidence-Ratee Voting
In this appendix, we provide additional results of our experiments using confidence-rated voting for CART tree-based learners (Section 6.7). Figures 14 and 15 show the anytime behavior of the considered boosting approaches using standard CART trees and confidence-rated CART trees on depth 1, 3, 5, and 10 (top to bottom) decision trees, for the twonorm and waveform datascts, respectively. For visualization purposes, we split the methods over three columns, ensuring the axes have the same range. As mentioned in Demiriz et al. (2002), tree stumps have too little confidence information and therefore confidence-rated boosting has little effect. On depths 3 and 5, we somctimes see slightly improved anytime behavior of confidenco-rated troes in the early iterations, especially for NM-Boost, QRLP- Boost, LP-Boost, and ERLP-Boooe However, the performance difference is never significant or structurally observed for all datasets, and the final performance
35

---

Published in Transactions on Machine Learning Research (10/2025)
Table 11: Testing accuracy and number of non-zero weights for different boosting methods for a reweighting experiment using 100 depth 5 trees generated by Adaboost. A star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics. 1 Adaboost hyperparameters were not tuned for the reweight experiment.
NM Hoott
QRLP--Boot
LP-Tlook
CD Daset
ERI CRLP-AE -oout
MD Dosett
Mahhott
Dutant
Acc
Cole
Adc.
Cub.
Acc.
Cubl.
Adc.
Cub..
Acc.
Cols
Adc.
Cub.
Acc.
Cida.
loveat CHEEET
6.37 IUDE
EJ6S
0,02"
ICC
(USS
0,549 EUSH
dabeto
072) 1U114
KTBJ 9303
6.741 0.0
L:748 0.20
ICC
0L553
0.755 (U12
AVTUAO Erallt
0590 [UG1
2,55
L208 2:00
ICC
0U12
hear
098
BATE 9192
0.39'
L255
DE
ILSTS
UST
1010
Image
0336 LUKE
ROCE 3768
0.57
8557
ICC
0S8
C002
0.55 0.96
Zaparaa
1028 0.90
ROSE 3764
6557 004
0935'
ICC
0.20 0U96
sike Bare
6S30 Jum
0179
ICC
0.565 0U3
xpllo
0554
DCC
0,355 1U90
Eayaad
0330 [U64
RONG 3101
0540 5.00
ICC
033
0002 8.860"
0.80 0U22
Ctankc
670 1014
BUKG 3102
100
6.77 0.9
6.79 0.04
ICC
6011 0.33
(J01
0.722 0.327
Desnarn
(32)
100S
5563 0.0
0555
ICC
(002
toge
10G3 3162
0.33
0.23
DCC
OUR2
0.325 0U96
sdelt
63i1 1006
100
3 1.000
ICC
E531 0000
0800-100 0U39
compas peopablia
eSG 6014
D033 3709
8:65 0.0
56
EXK7 8.07
ICC
0.569 0.316
emppgyront CA22Da
6707
2700
6.755 082
ICC
674
u7 0U96
implirment TX2208
0,37 1004
26
14
6.71 0
6743
0337 &
0,50
0.75 0U90
public caneagg C33008
0.000
0000 9161
6313" 1001
0206-
100
0204
public ranwagg TX3818
0.50 0000
0558 1165
6:15 6-0
16
0952 0.301
0J22
0.90 0.300
mandionn accandary
0.300
B00K 3765
0.59
0555"
100
0.930 01300
Table 12: Testing accuracy and number of non-zero weights for different boosting methods for a reweighting experiment using 100 depth 10 troes generated by Adaboost. A star* marks the best among totally corrective methods. The last row shows the mean and median for both statisties. 1 Adaboost hyperparameters were not tuned for the reweight experiment.
NMG Bunst
QRLP-Boott
L.P BonBo
OG-Boott
ERI Booot
MDD Bonet
Tatast
Acc.
Dal..
Cole
Cdlc
Cale.
Clos.
Code
Aoc.
Csle.
Imaga
ringoera
LoKe
DK)
291
0.525 0.09
1008 LUKE
113
9524
6001
aoher dace
1/82
13
(U96 0082
0 9.09
splicr
1301"
0392
9592
Eayrold
0540 3124
DOMP 0/124
0.36
5503
EJ6 EXG4
Dtandi
LIT
0353 1113
83
0270 GUIT
5770
6.76 5/00
teenora
E984 2
0383
DNI
391
TURT EURO
113
5583 9164
Baveforn
EAL 2.03
0.56 3.50
100
06
153
5553 3.60
300
E:031 6X00
adut
EAEE &
0333 0.32
DW)
123
1536
3102
320
5.00
renpes propuiliios
Loot + 1017
$2
0037 8003
(00
0/04 0015
100
BAAS' 00113
113
11557
0010
1000
BIKE 6-03
130
repplattinn CASIIL
6/444
4334
100
0228 0008
0011
100
191
5717
616)
6/255 6000
replacment TXin1s
6.73 2003
0353 3134
64
5.7A 0.001
77
0.720
100
I/76 1000
18
5753
0163
6/000 6.00
public coeeage CASILS
2306
39
4309 1112
U220 DURG
191
IUTEO 2104
109
113
5700
3164
6314 5180
130
public comrgg T'ans
1807
2 1000
3
1353 1134
19
UUS0
0084
08
(3:44
11003
109
9203T
19
1M47
9162
19
E063
130
mudhroom mcondary
3557"
2 0/30
13
0397 2 BICC
93
1560"
00.00
34
0L997'
à 5306
100
8368" (100)
80
3505
3162
10
6066
& EXE0
330
1839/
(78/4)
(08)
(108 18
(381 (0.59)
013 863
0,53" 1084
151 1000
15.// (155
MS51
7927 (80.
910h (000)
(10) (16)
36

---

Published in Transactions on Machine Learning Research (10/2025)
is often identical. Figure 16 displays the testing accuracy and sparsity of the different boosting approaches, averaged across all datasets, for both standard CART trees and confidence-rated CART trees, for the different tree depths. Finally, Tables 13, 14, 15 and 16 show the testing accuracy and sparsity of each tested approach for each individual dataset, for confidence-rated trees of depth 1, 3, and 10, respectively.
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Depm
Depth
Deph
Death
Depth
Seath becnem
Figure 14: Anytime behavior for the twonorm dataset and 1, 3, 5, and 10 depth CART decision trees compared to confidencc-rated trees (dashed line), error bars indicate standard deviation over seeds. The methods are split over three columns for visualization purposes.
37

---

Published in Transactions on Machine Learning Research (10/2025)
NM-Boost
QRLP-Boost
LP-Boost
CG-Boost
ERLP-Boost
MD-Boost
Figure 15: Anytime behavior for the waveform datasct and 1, 3, 5, and 10 depth CART decision trees compared to confidence-rated trees (dashed line), error bars indicate standard deviation over 5 seeds. The methods are split over three columns for visualization purposes.
38

---

Published in Transactions on Machine Learning Research (10/2025)
Test Accuracy Ensemble Sparsity Depth
Accuracy vs Ensemble Sparsity Depth
BoM-BBost
eNM-Boost
1.5
aNM-Boost (CR)
RRLP-Boost
CG (CR))
Co-Bo
LP-Boost
ANM-BoOst (CR)
Boost (CR)
CG-Boost (CR)a
CG-Booste
Avrragee Bottn Accrozy
Avwrage Texting Accureeyy
ORLP-Boost
P.P-Bostt
0,00
ERLP-Boost A MDD.Boost CR)
2.00
0.7
@ERLP-BoOSS
QRLP-Boost (CR)
MMD-Boost
P-oosstt (CR)
ERLP-Boost (CR)
4QRLP CRLP-BBok P-Boost (CR)
-DD Boost-
GRLP-Boost (CR)
aMD-Boost (CR)
12
Average
Average
lisdd
Tast Accuracy vs Ensemble Sparsity on Dapth 5
Tast Accuracy vs Ensemble Sparsity on Depth 10
eNM-Boost
CG Boosto
P-Boost (CR)
Co-Bo
#ORLP-ROOR ANM-BOOSt Roost
CG- CG-Boost (CRJA
Coott (CR)A (CR)A
Average Testing Accurscy
LLP-Boost
Rowrage Sesing Accuracy
ERLP-Boaast
QRLP-Boost (CRJA
M-ost
NM. Boost (CR)
RL Poostt
ERLP-Boost (CR)
BRRLPBBoost
6,05
D-B-oost
CRLPtBoost (CR)A
P. P-Boost (CR)
LP-Boostt
aMD-Boost
0.00
MDD-Boost (CR)
MD -oD-BBost-aoo (CR)
Average Number of Colamns Used
Average Number of Colonn lived
Figure 16: Average testing accuracy compared to average ensemble sparsity over all datasets for 1, 3, 5, and 10 depth CART trees with either hard voting or confidence-rated (CR) soft voting.
Table 13: Testing accuracy and number of non-zero weights for different boosting methods using confidence- rated CART trees of depth 1, averaged over five seeds. A star* marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
NM--Booe
-Ro.t
L.-Boott
OG-Boost
KRLP-Boost
MiD-ooost
Datasct
Cols.
Cols.
Cols.
Acc.
Cols.
banana
0.075' 0.016
0,021 0001
0.025" a 0.016
0.675" a 0.016
0,000 0.006
100
0U925" 4 0.00
breat DISCHr
0.785 0.050
0.501 0.058
35
0.770 0.058
0,792
0.010
100
0.792 0.058
08:55 4 0.051
22
diabetes
0.785 0.019
0.021
0.019
0.026
0.764 0.020
0.020
17
cradit
0,807 0,006
0,786 0.024
100
0.752 0.007
0,700 0.027
0.708 0.024
100
0.505 0.021
45
heart
0,522 0.022
0.028
0.064
0.813
0,005
0.707 0.045
0.025
21
Imsage
0,830 0,010
0.507 0.000
15
0.833 0JULT
13
0,863 0.003
100
0.784 0.024
12
0,708 0.025
12
fingnorm
0.929
0.018
64
0.002
0.001
0,002
0.503
0.002
30
solar Hare
0.710 0.071
0.738" à 0.064
31
0,612
0
0,718" 2 0,008
100
0.738 1 0.047
0,710 0.071
14
splice
0/033 0,007
0003
0.000
0.915
thyroid
0.940 0.055
0.916 0.032
0.922 0JULT
0,944 2: 0,0002
100
0.307 0.055
0.944" 4: 0.0032
38
0.099
010255
Ewnnarm
0.881 = 0.001
0.917
0.002
100
0.960 0.005
58
0.001" + 0.005
100
0.910 0000
100
0.561 1: 0.001
16
saveform
0.008
0000
shalt
0.811* = 0.001
15
0.786 + 0.014
5
0882 0.005
12
0.813 0000
0.510 0.00
145
0.512 1: 0.001
144
coupрae propublica
0.066
0.018
100
0.015
0.016
0.017
amplayment CA2018
0.710" = 0.003
17
0.733 0.008
18
0.Toy"
+ 0.003
18
0.710 + 0.005
76
0.735
0000
8-
0.751 0.003
11
umplayment TX2016
0.741" 0,003
0.006
0.744" 0.003
0.008
0.006
public coverage 2010
0.600 6001
27
0.408 0.005
100
0.650 0.005
0.690 0.066
100
0.685
0.000)
100
0.200" + 0.005
55
TX2018
0.002
0.002
0.002
0.002
67
mushuoom secoudary
0.757 0.006
0.507 4: 0.073
0.517" A 0.005
64
0,310 :: 0.004
0,776 d: 00000)
23
0,763 d: 0.008
22
Mean/ Meelan
0.506" 10, 901*
21 9/17.5
7888
51.5/10
0.701 (0.799
16. 16/8/7
9990
97. 5,15
0,785/00776
82,029955
0.797/0880
21.2/19
39

---

Published in Transactions on Machine Learning Research (10/2025)
Table 14: Testing accuracy and number of non-zero weights for different boosting methods using confidence- rated CART trees of depth 3, averaged over five seeds. A star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
NM-Boot
QRIP-Booot
LP-Boost
CG-Boodl
ERLP-Boot
MD-Boust
Dalaset
Acc.
Culs
Anc.
Cole
Acc.
Cula.
Aue.
Cale
Acc.
Col..
Acc.
Col..
0,600 0014
0.315
0,675' 0.015
0.500 0.014
100
0.000 0.014
20
breast CanOsE
0.888 a 0.019
17
0,535" 2. 0.026
0.R25 IJ035
15
0,584 4: 0.047
100
0.804
0.004
50
0.785 2: D.B28
21
diabetes
0.702 DM2
0.007
0,758" 0,019
11
0,722 0.005
100)
0.036
0.730 (0035
german credit
0,755 0.08
50
0.83 0.005
0.855 0.038
72
0.852 0.002
100
0.97
0.030
100
0.776 4: 0.000
Inart
0.811 0.044
0.867 0.000
0.967 0.040
31
0,578 1 0.025
100
0.52
0.042
100
0.774 1: 0.072
20
imagee
0,947 + 0.005
0.926 0.015
0,063
0.954 0.007
100
0.876 4: 0.025
Yilggoorm
0,507 + DJ00G
86
0.930 : 0.000
100
0,013 00004
69
D.00S" 0.000
1001
0
0.006
100
0,867 = 0.012
87
0.014 0.074
0/079
xplien
0,975 + 0.005
34
0.967 : 0.008
100
0,915 0.001
69
0,775' 0.066
100
0352
0.001
100
0.005 +: 0.005
45
Uhyroid
0,949"
0.300 0.024
0.043 0.085
0.024
0.004
litonic
0,504 # DUB14
11
0.530 # 0.002
100
0.803 =: 0.127
21
D.823" 0.022
1001
0
0,026
100
0,805 #: DUR24
100
twonorm
0,061 DJM0S
0.935 0.005
0,050 B000
74
DUNGS" 0.000
104)
U112 0.200
0.189
10029
6G
wavodarm
0.911 0.011
94
0.800 0/001
0,911 0.000
82
0.01" 0.000
1(0)
0,885
0.000
0.815 + 0.006
adulk
0.817 +: 0.002
88
0,817 4: 0.200
0.817 :: 0.004
82
0,317 4: 0.001
96
0.810
0.002
100
0,818" 1. 0.000
41
comupı propublics
0,005 0.012
0.668 0,005
0.008
D.00D"
0.014
100)
0,607"
# 0.013
0.061 #: 0.006
employment CA2018
0.746' 0.002
69
0.737 =: 0,000
0,743 0.053
74
0.743 4 0.0022
76
0.745
0.000
100
0.737 =: 0.003
16
employment
0.001
public coverage CA2018
0.708 1 0.004
92
0,202 a 0.014
0,711 :: 0.005
96
0.711 1 0.005
100
0.205
0.002
100
0.715" 4. 0.000
96
public TX2018
0.005
0.851 0.001
0.862
0,462
0.002
100
musibooou secondary
0,988'
0.001
75
0.700 #: 0.085
0,598"
0,000
82
0.008" 0.001
86
0.802
00000
57
0,895 # 00033
28
Moan/ Medion
40.5/42.5
0,314/0.826
67,0/100
0,533 10,537
54.5
0.833" /0.943
97,5/100
0.810/0.821
96.2/100
0.802/0.706
45.0/43
Table 15: Testing accuracy and number of non-zero weights for different boosting methods using confidence- rated CART trees of depth 5, averaged over five seeds. A star* marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
NMs-
Qooet
Do-St
CG-
KRLP: Boost
MD-Book
Dataset
Acc.
Cols.
Acc.
Acc.
Cols.
Acc.
Cols.
Acc.
Cols.
Acc.
Cols.
bonana
14
0,6T1 0,014
DU070 0.014
100)
0,670' # 0.004
breaet cancer
0,899 + D013
0.561" 4 001E
100
0838
DU5T
27
0.511 4 0.012
1(8)
0.55
00008
1000
0.717 4: 0.035
58
0.015
0.018
german crodit
0,882 +: 0.02
25
0.874 1 0.204
100
0,887
0.009
80
0.582 4: 0.029
100
0.861
0.002
100
0.825 4: 0.018
44
heart
D.225
0,878" 0.000
D8875 0.022
100)
0.967
0.014
Image
0,809 + 1000
19
0.851" +: 00000
100
0,003 H: 6000
4%
BUG51" 0.00
1(4)
01330
0.007
100
0.111
4: 00077
7H
ringuorm
0333" 0.007
82
0.16
0.000
0.937 000G
70
0:957 0.005
100
0.899
0.008
100
0.835 1: 0.017
47
solur
0,663 0.069
0.854
0.041
0.611
0.661 0.001
100
0.090
0.000"
splice
0.873 + 0.005
20
0.075 4 0,207
100
0,080 0000
84
D.081" 0.000
100
0
0.000
100
0.967 1 0.006
100
Hhyrold
0,800 00024
0,003
0.80 0.003
0.944
(00)
0.921 # 10034
titanie
0810" 0.001
6
0.800 4 0.012
100
0,100 0.025
14
0.710 4 0.005
100)
0.800
0.035
100
0.796 + 0.078
18
0.903 0.05
0.206
0,900
0.001"
0.900 0.012
suveform
0.921* = 0.011
67
0.12 4 0,208
100
0.015 =: 0,008
76
0.220 4: 0.010
100
0,859
0,007
100
0.807
4: D.006
02
adule
0,515 0.002
0.815 0.000
0.81T
90
DSSES"
0.002
0,518"
0.002
01318"
622
compas propabiiia
0.065 + 4.014
35
0.000 0.011
100
0.005 0.000
61
11670" 0.014
100)
0/057
0.015
100
0.055 4: (1016
688
smploymert CA2018
0.768 :: 0.002
69
0.760 0.006
0.718 0.008
75
0.71P" 0,000
75
0,788
3. 0.005
100
0.741 5: 0.008
S1
exppooyment TX2018
0.766 +: 0.002
0.002
0.758 0.000
91
0.746 4: 0.006
public coverage CA2018
0.712 + 2.005
96
0,707 a 0,202
0,736' 0,005
99
0,714 d 0.005
1001
0.208
0.000
100
0.715 4: 0.004
62
public coverage TX2018
00002
0.000
0.522
0.552
0.001
(00)
mushroom mecondary
0,905 1 0.000
44
0991 1 0.041
0.500" 0.000
80
00000" (0000)
66
09100
0.000
91
0.089 F 0.030
440
Moan/ Median
0853500835
50,5215.5
0.830/ 6.835*
8688/10
0.853" 10.545
59.5/76.5 5
0,831/00.555
97.4 97.4/100
0.807/0 858
95.6/103
5,115/10801
02/0/62
40

---

Published in Transactions on Machine Learning Research (10/2025)
Table 16: Testing accuracy and number of non-zero weights for different boosting methods using confidence- rated CART trees of depth 10, averaged over five seeds. A star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
NM-Boust
QRLP-Boost
LP-Bous
CG-Boodd
ERLP-Bool
MD-Boood
Dalaset
Acc.
Cola.
Acc.
Cole.
Acc.
Cule
Ane.
Coda.
Acc.
Cula.
Acc.
Cole
0,500" 6.014
0,570r
0,570
100
0.770
0.014
breast CanesE
0,519 4. DUILD
0,830 0.024
74
0,510 4. 0J125
25
0.808 :. 0.025
100
0.825 =: 0.01
51
D.845 2 0.087
diabetes
0,714 DM0
0.7UI" 0.026
100
0,017 0.002
0.734 0.005
0.087
99
0.009
german credit
0.995 0,009
0.887 c.016
100
0.875
0.002
05
0.851 0.091
0.872 0.700
87
0.571
4 4-0.022
Inart
0.837 1 I.022
0.835 0051
0.831 1 0.012
0.41 0.025
100
0.65 0.015
0.589 0.065
imagee
0.955'
0,862 4: 0.011
47
0.952 0.011
0.041
88
0.015
Yinggoorm
0 + 0.004
21
0.924 0.006
100
0,905 # 0.005
96
0,505" + 0.008
100
0.915 00008
100
0.919 0,000
0.006
0.019
0.000
0.075
xplicn
0.963 + 0.005
0,900 0.06
100
0.965 1 0.00P
76
0,909" 1 0.005
100
0.915 0.000
100
0.917
0.005
100
Uhyroid
0,949 0.025
0.363" 0.029
0.025
0.023
30
0.004
litonic
0,500 # D.017
12
0.774 =: 0.030
100
0,789 # 0,015
24
0,503 #: 0.027
100
0.797 = 00027
82
0.796 4: 0.003
100
twonorm
0,845 + R1005
0,888 0.006
0.891 + 0.0055
0,965" 0.008
0.14D
300
0.102
wavodarm
0.912 0.003
0.:7 0.06
100
0.913 + 0.002
98%
0.805" 0.000
100
0,800
0.011
100
0.905
00000
aduls
0 a: 0.002
0.8.6 0.002
100
0.516 1: 0.002
9.3
0.816 :: 0.202
0.816 0.002
0.316
000002
comupı propublics
0.060" 0.014
0.655 0.014
0.064 + 0.014
85
0.605" 0.004
0.015 0.018
100
0.014
employment CA2018
0 + 0,005
24
0.747 0.000
100
0.743 + 0.002
15
0.778 0.001
0,70"' 0,0412
100
0.742
000012
employment
0.001
100
public coverage CA2018
0,710 1: 0.005
36
0.711 0.066
100
0.695 1. 0.007
99
0.715" 1: 0.005
100
0.708 0.006
100
0.607 a: 00000
61
public TX2018
0.002
0.002
0.849
100
0.002
musirooou secondary
0,050'
0.000
14
0.389' + 0.000
100
0.999"
0.000
76
0,503" #: 0.000
0,083
00004
100
0.990 #: 0,002
Moan/ Medion
0.825/0,825
13/8/10
0831/0811
85,0/100
0.823/0.826
6466/94.
0.8TE" /3.822
97,0/100
0,825,0
$3.6/100
0.815,0,511
80.3/87,5
D.7 Experiments with Optimal Trees as Base Learners
We report in Tables 17, 18, 19, and 20 the per-dataset performances of the different considered boosting approaches, for optimal decision trees of depths 1, 3, 5, and 10 (respectively) trained with the Blossom algorithm. They complement the results provided in Section 7. Figure 17 shows the accuracy-sparsity trade-off of ODT ensembles in comparison to CART ensembles, aggregated over all datasets.
Table 17: Testing accuracy and number of non-zero weights for different boosting methods using optimal decision trees of depth 1, averaged over five seeds. Bold highlights the best accuracy among all methods, while a star* marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
NM Boast
QRI P. Toost
IP Boot
CD Fooo
FRI P. Booe
MD Tooe
Adalwret
Datnset
Anc.
Cdla
Anc.
Cdls
Anc.
Cala
Are
Coby
Are.
Oob.
Are:
Oob.
Are.
Oob.
390 (1C)
02
156 8001
0.113
194 0263
1.155
0A0E 0.315
6911 0206
1121 1/21
0,14"
03314"
0.14'
200
8.32
(012 0.327
6911 02204
1911 L127
1535 1/22
57
0.99 0121
1L587 1/22
0/50 1.82
6SH 0.12
0.877 1063
DvonOCTS
0.952" 2 tue
1541: 1164
0599 1364
0.991 1000
000
1967 1119
0002 (1.10
6941 1094
voodiee
0,990 2 tue
57
1555: 1164
0,990 1080
52
0,011 tu8e
0980 11.377
0303 UURG
sdall
8814 L11
0,14"
09912 1..30
0803 1080
euppe prppistee
0499 Lo0
0,71" 0005
14
0180 0012
0491 1011
110
0453 0017
116
erpplemmnn CA3318
078)-(003 (403
16
0.7" 0006
76
a 0463
9780- 0000
100
0758 + 0.390
34
6738 0006
100
reppoymnnt TX2018
071- (40)
91
0.315' - 0004
72
071: 0063
10
0311 0100
100
6723 + 0.002
6265 + 0.30
39
6733- 0.06
100
public ammagg CABl1A
8680- E,E5
7
0.004" 6000
0 0005
3.00 0006
100
0.TNE 4: 0.00
35
6.760 0.003
53
6.00 0.00
1n0
pilic orerrge TXam14
1551 L103
14
0,30
2 1080
331
0121 0102
5121 1882
240
1053 1.1
73
1A6 2 01.30
33
0X41 1U80
110
meleum accndery
0508 LSES
18
1755 6164
08
0317" 1 1004
12
0 2 1084
100
35
0740 5 0.307
34
6734 0000
116
(0310
B58 / 1835
365
6/81/88
308/
0700/0407
41

---

Published in Transactions on Machine Learning Research (10/2025)
Table 18: Testing accuracy and number of non-zero weights for different boosting methods using optimal decision trees of depth 3, averaged over five seeds. Bold highlights the best accuracy among all mothods, while a star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
Dutnee
Acc
Cote
Apc
Cots
Adc
Cota
Arc.
Cuta.
Acc.
Coto.
Acc.
Cob..
Arc.
Cols.
0921 6007
3335 6160
1859
199
0.310
0.009
Baroi
3191 E005
3555 5061
0,43"
0108
199
6011- 0005
8913 c/69
11
3930 5/61
092 5105
91
(463
199
0.177
6813 0.066
1396 E361
96
0153 5765
0.992
(U6S 1.30
199
(UNE 1.99
0/85 0.36
6551 009
1995 LAC3
45
0394 1/65
05
0.11
D.00 0.00
199
0.30
0284 0286
1997 E3K2
1309 1362
333
0308 EXEL
12
1.00
6333 0280
propeiiiie
1855.2 LJ0)
0135 1104
19
0,600 LU14
URRT 10015
191
109E 11.11
116
U.87 0.316
EX85 1011
CA3938
0793 LXK
14
0,54" 00R
333
24
1/39 1.99
41
WTT 3.92
0.78 0.330
6341 MURG
empoymmnt Txatts
073 LXK3
04
1338 5165
331
871T 9163
U/T 0.00
-5
ILTM 3.5
0S8 0.38
6T34 0084
public smosgg CA2215
3.56 EXCS
15
3399
1/64
330
3785 EX67
06
KITS 1097
199
0.122 3.00
100
0,07 0.399
89
E311 0006
100
polle smrrage TX2015
0550 LAK2
0352
1/63
330
0.59 6X62
1058 à 0.90
181
0.553 0.002
55
0,82 à 0.30
35
E381 1080
116
molenm accndary
0955 EJES
14
0199 1001
78
0.539 E365
04
0,992 2 0.00
05
10TS 1199
15
(003 4 0.338
0207 00113
106
MeanyModlen
300/300
640
70085
780
0.08
05//4 0,837
948 1903
(181
0801/951
209/213
085/9551
100 (M)
Table 19: Testing accuracy and number of nou-zero weights for different boosting methods using optimal decision trees of depth 5, averaged over five seeds. Bold highlights the best accuracy among all methods, while a star* marks the best among totally corrective methods, The last row shows the mean and median for both statistics.
NM Revei
QRIP Boost
LP Bood
CG Rose
FRLP Book
MD Raoe
Dalnest
Cale.
Cili
Arc.
Cdda.
Art.
Cids
Cake
Cdla.
Colo.
6.660
0384
8582
0.20
6,006
8607" 4:3.55
0317
819)
E607 2103
190
0/66
0311
6.556 CO05
6.56" 1.1334
15
032 1104
0555 1384
1008 19055
230
1015 1-0555
54
0.52 0163
0521 DUE
whe Bar
6,800 2:188
088
L008
US84 1155
291
US2
0352 2.16
0155 (U23
116
splev
L997 u.M
um0 2 1103
U.P 138
1357 1105
180
UUT 1100
0.73 0160
6356 2 U1A
116
(963 0.25
0068 1101
0553 0061
DOCE 0338
19
URS 11087
033 0167
9 0183
116
Uloeir
[a11 + 037s
0517 + 0004
553 0003
676 + 0.33
130
030 0.00
0400 - 0101
6A10 - (003
110
54
0302 1003
54
110 0008
76
130
698 0.02
54
037 4 6007
110
883 + +...0
75
6317 + 3/09
07
110 0013
97
600 0.012
130
036 011
56
052 5065
24
6.85 - C001
100
sdult
E317 0.0
84
6NIT 3002
66
1517 0008
RSTE 0.92
130
6317 0.00
100
03030" 1000
a 0003
100
compas propiikka
EOE5 6013
11
092 a 1109
9476 6014
0.670 0063
120
0967 4812
3520 EX03
01
0.21 0002
110
нирроулни CA2018
L 0.9
92
0.790 6062
230
478 1000
230
0.700 3101
04
3765 EX0C
4746 0X02
110
sаpооymsu I32915
L775 0.94
91
0:30 3183
230
0334 1000
20
130
0761
1 3105
12
3.20 2 0162
0796 UUE
110
pulie covenge CA2208
(120 0.96
13
0224 2 3102
230
6.14" 101
96
KXI2 1002
16
6713 1775114055 1.0555
(90
ANT 2 0102
116
polie covenge T32208
1,23 1191
130
1992 1080
19
1058 2 1.92
190
1053 11122
82
0550 D1RC
17
0331 LU8
116
meleeon scondtty
(355 1 1198)
W90 5 3186
6/19 2 1080
WAMM 1191
16
1083 1-18L1
24
3591 2 0163
25
0197 0000
116
915
371/910
050
42

---

Published in Transactions on Machine Learning Research (10/2025)
Table 20: Testing accuracy and number of non-zero weights for different boosting methods using optimal decision trees of depth 10, averaged over five sceds. Bold highlights the best accuracy among all mothods, while a star" marks the best among totally corrective methods. The last row shows the mean and median for both statistics.
LP-Boaet
KHLP--ooot
Datsett
Are.
Are.
Cdll
Are.
Cakl.
Apt.
Cale.
Ary.
Cikl.
Are.
Clak.
Are.
Cull.
0.670" DALL
BLSTO' 8.64
0,870'
0.670" EU314
0.070' 1.311
6-1.14
Icesst CROSE
0.835" EVGE
E/G3
34
4715
38
0.17 LUB0
94
0.700 5-1115
Brran CTdR
8:1825
Imag
Faggram
propattlias
emplyyane
empkyaue
Mean/ Musiian
6999 / 0666 160
059//50 434//00 083 1987
13 345
8,85 10.52
06/0 1080
949/ /365
5/ 190 0331 (0.5)) 8855 30.
/
95, 100
Test Accuracy vs Ensemble Sparsity on Depth 1
Test Accuracy vs Ersemble Sparsity on Depth
NNM-Boost
WQRLP Boost (ODT)
@ORL--BOOE CG-Boost (ODT)a
Boote
6,05
NM- MM-BBoost
LP-Boost
#NJM Noos- (OPT) MLP-Boost (ODT)
boose
Rvorsqe Teddngg Accurac)
A.P.Boost
RLP-Boost (ODT)
Avwrage Testing Accunnry
0,003
LP-Boost (ODT)
CG-Boost tOD
CG-Baost
ERRLP-Boost
Ad Adoosss Adaboost (ODT)
0.00
NM-Boost (ODT)
ORLP.BooSt (ODT)
MiD-Boost (ODT)
@RLP-Boost (ODT)
E RRLL. Boost #RLP--BooS (ODT)
eMD DMD-Bame Dnost
aMD- Boos-Btot....
Boost (ODT)
eap
120
Average Number columess Used
Aver Number of Columns Used
Test Accuracy Ensemble Sparsity Depth
Test Accuracy Ensemble Sparsity Depth
3.44
HNMMBooost (ODT) NM -MM-Boost
Ad (ODT)*
Adaboost CG-Boost
CG-Boost (ODT)*
Avcroge Tosting Acoursc
110
@RLP--Book LPostttt (ODT)
CG-Boost (ODT)M
Adabooste CG-Booge
Avwrage Teating Acturess wey
0.004
Adaboost (ODT)
WORLP.Boost (ODT)
P-Boost
6,022
aMD-Boost (ODT)
3.4
NM- MM--ooost
ERLPPBooot
#RLP-Boost (ODT)
ERLP HERLP800O Boost
BELstBoost (ODT)
0.00
NM-Boost (ODT)
ORLP-Boost
0.000
#RLL-Boost (ODT)
MD-BoosE
-MD--Boo Boott
1000
LP-Boost (ODT)
MMD-Boost (ODT)
0002
LP-Bosst
100
Number Colames
Number of Colimna Used
Figure 17: Average testing accuracy compared to average ensemble sparsity over all datasets for 1, 3, 5, and 10 depth CART trees or optimal decision trees (ODT).
43


Reviews:
[{"review_id": "eDgOajSp54", "reviewer": "Reviewer_Gecy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Contributions:\n1. Comprehensive Benchmarking: Perform the large-scale comparison of six LP-based boosting formulations against leading heuristic boosting methods across 20 datasets.\n2. New Methods: two novel formulations, NM-Boost and QRLP-Boost.\n3. Base Learner Study: Examine the impact of different base learners within boosting frameworks, including standard CART trees and optimal decision trees.\n4. Empirical Analyses: Provide in-depth evaluation not just of accuracy, but also sparsity of ensembles, margin distributions, anytime performance, and sensitivity to hyperparameters.\n\n\nKey Strength:\n1. From Contribution 1&3&4, the paper is very comprehensive and comparative. In addition, the Experiment results are also very detailed and convincible.\n2. The intuition and introduction of two new methods are very clear and easy to understand. The formula is also very detailed.\n\nWeaknesses:\n1. The full code is only \"available online upon acceptance\". What about using an anonymous way for now? Otherwise, it is hard to justify reproducibility.\n2. May discuss more about choosing hyperparameters. In Fig 6, except for QRLP-Boost, the best hyper-parameters for other methods are extreme (largest/smalles among all 10 choices). \n3. (Minor) Some figures are hard to identify. For example, in Fig 6, there are too many lines with similar colors. In Fig 9, some outliers make the y-axis very large such that the box is very small.", "claims_and_evidence_yn": "Yes", "claims_explanation": "As long as authors can clarify the weaknesses, the conclusion should be sound as it is reproducible and has a very clear evedence.", "audience_yn": "Yes", "audience_explanation": "And I believe some TMLR's audience should be very interested in LP-Based Ensemble Methods. I believe Boosting remains one of the most widely used ensemble methods in ML. And in this paper, there are comprehensive comparisons to strong baselines.", "requested_changes": "See Weaknesses.\n1. Reproducibility is important, especially for this paper which examines thorough experiments. \n2. Need to explain why for some methods, the best hyperparameter is the \"extreme\" one among all candidates.\n3. (Minor) Some figures could be easier for readers to get the key message.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lsn6Ni92uE", "reviewer": "Reviewer_eVip", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a thorough evaluation of the performance of boosting approaches. Multiple boosting methods, including two newly introduced ones, are evaluated across diverse datasets and metrics.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The work provides a thorough analysis of boosting methods using various metrics. Despite the advancements in deep learning approaches, boosting methods remain among the best for modeling tabular data. This work provides an excellent foundation for researchers who are interested in comparing any non-boosting approaches with the benchmark boosting method presented here", "audience_yn": "Yes", "audience_explanation": "Despite the popularity of deep learning approaches, boosting methods are still considered among the best for modeling tabular data. This work provides a strong foundation for researchers interested in comparing their non-boosting approaches against boosting methods.", "requested_changes": "I would request authors to provide the solutions of the two proposed LP problems in (9) and (14), given that LP typically has analytical solutions. If that's not feasible, please explain why.", "broader_impact_concerns": "I didn't find any ethical concerns.", "additional_comments": "Could you please elaborate on the role of $p_\\text{neg}$ in (9)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "QesXiFBATc", "reviewer": "Reviewer_B18U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a comprehensive empirical study of totally corrective boosting methods based on linear programming formulations, which adjust the weights of all base learners at each iteration. It compares with six LP based methods, NM-Boost, QRLP-Boost, and AdaBoost, XGBoost, and LightGBM. It is evaluated on 20 diverse binary classification datasets. \n\nThe paper introduces NM-Boost and QRLP-Boost methods that perform well on shallow trees particularly.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The paper provides empirical study across 20 diverse datasets with results presented in multiple tables and figures for accuracy, sparsity, margin distributions, and hyperparameter sensitivity. Observations are shown. \n\nHowever, the paper can be more clear and convicting to show the codes that generate the figures and results in the tables.", "audience_yn": "Yes", "audience_explanation": "The empirical study of LP-based boosting methods, the sparsity benefits, margin distributions, and comparisons to heuristics like XGBoost  will be interested to some audience. \n\nHowever, more applications and discussions on multi-class problem are better.", "requested_changes": "1. Lack of computational cost analysis\nThe paper does not quantify its computational complexity or runtime compared to heuristic methods like XGBoost and LightGBM. \n\n2. Binary classification limited\nThe study focuses on binary classification only, limiting its applicability to multi-class or regression tasks, which are more common in applications. \n\n3. The paper lacks discussions on efficient tuning strategies.", "broader_impact_concerns": "The paper includes the adult dataset for testing, and the concern like bias on rase and gender will be raised. It is better to discuss the risks and mitigation strategies of them.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)