Keywords: Ensemble Pruning, Probability Calibration, Convex Optimization, Simplex Constraints, Model Compression.

1 Introduction↩︎

Ensemble methods, particularly bagging (Bootstrap Aggregating) [1] and its extensions such as Random Forests [2], are among the most robust and widely deployed paradigms in machine learning. By training multiple base estimators on bootstrap samples of the training data and averaging their predictions, bagging reduces variance without increasing bias. However, this variance reduction comes at a steep computational cost. Large ensembles require substantial memory footprints and impose significant computational latency during inference, rendering them challenging to deploy in resource-constrained or real-time production environments.

Furthermore, traditional bagging relies on a naive uniform prior where every base estimator is assigned equal voting weight (\(w_j = 1/N\)). This uniform prior assumption is sub-optimal for two primary reasons:

1. Calibration Overconfidence: Uniform averaging of probability estimators tends to push ensemble outputs toward moderate values, but when estimators are correlated, it leads to poorly calibrated, overconfident predictions near class boundaries, inflating the Expected Calibration Error (ECE) [3].

2. Estimator Redundancy: A significant fraction of base estimators in a bootstrap ensemble are redundant or represent noisy sub-spaces. Treating them equally limits generalization capacity and wastes inference computations [4].

To resolve these limitations, we propose Simplex-Constrained Sparse Bagging (SCSB), a post-training framework that transitions bagging ensembles from uniform priors to sparse posteriors. By optimizing estimator weights over the probability simplex using out-of-bag (OOB) validation samples, we learn a sparse posterior weight distribution. Estimators with negligible weights are pruned completely, resulting in a significantly smaller ensemble. The remaining active estimators are weighted to minimize loss, improving both calibration and generalization.

Standard sparse coding approaches rely on Lasso (\(L_1\) regularization) to zero out weights [5]. However, when optimization is constrained to the probability simplex, the \(L_1\) norm of the weight vector is constant. Consequently, standard \(L_1\) regularization fails to induce sparsity. SCSB resolves this “\(L_1\)-simplex paradox” by using a concave quadratic penalty (\(-\lambda \|w\|_2^2\)), which forces weights to the boundaries of the simplex, yielding exact zero weights.

Our contributions are summarized as follows:

• We formulate ensemble pruning and calibration as a joint optimization problem over the probability simplex (\(\Delta^N\)), minimizing Out-Of-Bag (OOB) loss to avoid data leakage.

• We address the theoretical \(L_1\)-simplex paradox by introducing a concave quadratic penalty and provide the mathematical proof of its vertex convergence.

• We derive analytical gradients for both Classification (Log-Loss) and Regression (MSE) to enable efficient, fast-converging optimization via SLSQP.

• We demonstrate empirically that SCSB achieves up to 96% ensemble compression, yielding linear inference speedups and superior probability calibration while preserving or enhancing generalization accuracy.

2 Related Work↩︎

2.1 Ensemble Pruning↩︎

Ensemble pruning aims to select a subset of estimators from a pre-trained ensemble [6]. Traditional methods are dominated by heuristic search techniques (e.g., genetic algorithms, greedy search) and ordering-based pruning (sorting estimators by validation performance and selecting the top \(k\)) [7], [8]. While simple, these approaches do not optimize the weights of the selected estimators jointly and lack mathematical guarantees. SCSB performs joint selection and weight optimization within a unified constrained framework.

2.2 Stacking and Data Leakage↩︎

Stacked Generalization (Stacking) trains a meta-estimator to combine base predictions [9]. However, stacking on the training set suffers from severe data leakage, leading to overfit meta-models. Solving this typically requires expensive \(K\)-fold cross-validation during the base training phase. In contrast, bagging ensembles naturally provide Out-of-Bag (OOB) samples for each estimator, representing a built-in, leakage-free validation set. SCSB leverages these OOB samples to optimize weights without additional training overhead or validation splits.

2.3 The L1-Simplex Paradox↩︎

Sparse coding and model compression typically rely on Lasso (\(L_1\) regularization) to zero out weights [5]. However, when optimization is constrained to the probability simplex (\(\sum w_j = 1, w_j \ge 0\)), the \(L_1\) norm of the weight vector is mathematically constant (\(\|w\|_1 = \sum |w_j| = \sum w_j = 1\)). Consequently, standard \(L_1\) regularization fails to induce sparsity in simplex-constrained domains. SCSB resolves this paradox by using a concave quadratic penalty (\(-\lambda \|w\|_2^2\)), which forces weights to the boundaries of the simplex, yielding exact zero weights.

2.4 Probability Calibration↩︎

Probability calibration ensures that a model’s predicted confidence aligns with empirical accuracy [3]. Traditional calibration methods, such as Platt scaling [10] and Isotonic Regression [11], are applied post-hoc to the final predictions of the ensemble. In contrast, SCSB embeds probability calibration directly into the ensemble compression process by minimizing Log-Loss on out-of-bag samples, leading to naturally well-calibrated ensemble predictions.

3 Proposed Method: SCSB↩︎

3.1 The Base Ensemble and OOB Indicators↩︎

Let \(\mathcal{H} = \{f_1, f_2, \dots, f_N\}\) be a bagging ensemble trained on bootstrap samples of a dataset \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^M\). For each sample \(i\) and estimator \(j\), we define the Out-of-Bag (OOB) indicator variable \(I_{i,j}\) as: \[I_{i,j} = \begin{cases} 1 & \text{if sample } i \text{ is Out-of-Bag for model } j \\ 0 & \text{otherwise} \end{cases}\]

3.2 Leakage-Free OOB Ensemble Estimation↩︎

To evaluate the ensemble without data leakage, we compute the OOB predictions of the weighted ensemble. For a sample \(i\), the weighted prediction is computed using only the models for which sample \(i\) was out-of-bag: \[\hat{y}_i^{\text{OOB}}(w) = \frac{\sum_{j=1}^N w_j I_{i,j} f_j(x_i)}{\sum_{j=1}^N w_j I_{i,j}}\] This formulation ensures that the optimization target represents true generalization performance and prevents overfitting during weight selection.

3.3 Simplex Optimization & The Sparsity Penalty↩︎

We find the optimal weight vector \(w^*\) by solving the following constrained optimization problem: \[\min_{w} \mathcal{L}(w) := \frac{1}{M} \sum_{i=1}^M \text{Loss}\left(y_i, \hat{y}_i^{\text{OOB}}(w)\right) - \lambda \|w\|_2^2\] \[\text{subject to } w_j \ge 0 \quad \forall j \in \{1, \dots, N\}, \quad \sum_{j=1}^N w_j = 1\] where \(\text{Loss}\) is Log-Loss for classification and Mean Squared Error (MSE) for regression, and \(\lambda \ge 0\) controls the strength of the concave penalty.

3.4 Optimization Algorithm & Gradients↩︎

We solve the optimization problem using Sequential Least Squares Programming (SLSQP) [12]. To ensure numerical efficiency and fast convergence, we derive the exact analytical gradients.

Let \(D_i(w) = \sum_{j=1}^N w_j I_{i,j}\) be the sum of active OOB weights for sample \(i\).

3.4.1 Classification Gradient↩︎

For classification, let \(P_{i,j,c}\) be the predicted probability of class \(c\) for sample \(i\) by base model \(j\), and let \(Y_{i,c} \in \{0, 1\}\) be the one-hot encoded target. The ensemble OOB prediction is \(p_{i,c}(w) = \frac{\sum_j w_j I_{i,j} P_{i,j,c}}{D_i(w)}\). The gradient of the Log-Loss objective with respect to weight \(w_k\) is: \[\begin{align} \frac{\partial \mathcal{L}_{clf}}{\partial w_k} = -\frac{1}{M} \sum_{i=1}^M & \frac{I_{i,k}}{D_i(w)} \left[ \sum_{c=1}^C \frac{Y_{i,c} P_{i,k,c}}{p_{i,c}(w)} - 1 \right] \\ & - 2 \lambda w_k \end{align}\]

Proof of Classification Gradient: The multi-class Log-Loss objective on OOB samples is: \[\mathcal{L}_{clf}(w) = -\frac{1}{M} \sum_{i=1}^M \sum_{c=1}^C Y_{i,c} \log p_{i,c}(w) - \lambda \sum_{j=1}^N w_j^2\] Differentiating \(p_{i,c}(w)\) with respect to \(w_k\): \[\begin{align} \frac{\partial p_{i,c}(w)}{\partial w_k} &= \frac{I_{i,k} P_{i,k,c} D_i(w) - I_{i,k} \sum_j w_j I_{i,j} P_{i,j,c}}{D_i(w)^2} \\ &= \frac{I_{i,k}}{D_i(w)} \left( P_{i,k,c} - p_{i,c}(w) \right) \end{align}\] Using the chain rule: \[\begin{align} \frac{\partial \mathcal{L}_{clf}}{\partial w_k} &= -\frac{1}{M} \sum_{i=1}^M \sum_{c=1}^C \frac{Y_{i,c}}{p_{i,c}(w)} \frac{\partial p_{i,c}(w)}{\partial w_k} - 2\lambda w_k \\ &= -\frac{1}{M} \sum_{i=1}^M \sum_{c=1}^C \frac{Y_{i,c}}{p_{i,c}(w)} \frac{I_{i,k}}{D_i(w)} \left( P_{i,k,c} - p_{i,c}(w) \right) \\ &\quad - 2\lambda w_k \\ &= -\frac{1}{M} \sum_{i=1}^M \frac{I_{i,k}}{D_i(w)} \left[ \sum_{c=1}^C \frac{Y_{i,c} P_{i,k,c}}{p_{i,c}(w)} - \sum_{c=1}^C Y_{i,c} \right] \\ &\quad - 2\lambda w_k \end{align}\] Since \(\sum_{c=1}^C Y_{i,c} = 1\), the result follows. \(\blacksquare\)

3.4.2 Regression Gradient↩︎

For regression, let \(f_j(x_i)\) be the continuous prediction of estimator \(j\). The gradient of the MSE objective with respect to weight \(w_k\) is: \[\begin{align} \frac{\partial \mathcal{L}_{reg}}{\partial w_k} = \frac{2}{M} \sum_{i=1}^M & \frac{I_{i,k}}{D_i(w)} \left( \hat{y}_i^{\text{OOB}}(w) - y_i \right) \\ & \times \left( f_k(x_i) - \hat{y}_i^{\text{OOB}}(w) \right) - 2 \lambda w_k \end{align}\]

Proof of Regression Gradient: The MSE objective on OOB samples is: \[\mathcal{L}_{reg}(w) = \frac{1}{M} \sum_{i=1}^M \left( \hat{y}_i^{\text{OOB}}(w) - y_i \right)^2 - \lambda \sum_{j=1}^N w_j^2\] Differentiating \(\hat{y}_i^{\text{OOB}}(w)\) with respect to \(w_k\): \[\begin{align} \frac{\partial \hat{y}_i^{\text{OOB}}(w)}{\partial w_k} &= \frac{I_{i,k} f_k(x_i) D_i(w) - I_{i,k} \sum_j w_j I_{i,j} f_j(x_i)}{D_i(w)^2} \\ &= \frac{I_{i,k}}{D_i(w)} \left( f_k(x_i) - \hat{y}_i^{\text{OOB}}(w) \right) \end{align}\] Applying the chain rule, we obtain: \[\begin{align} \frac{\partial \mathcal{L}_{reg}}{\partial w_k} &= \frac{2}{M} \sum_{i=1}^M \left( \hat{y}_i^{\text{OOB}}(w) - y_i \right) \frac{\partial \hat{y}_i^{\text{OOB}}(w)}{\partial w_k} - 2\lambda w_k \\ &= \frac{2}{M} \sum_{i=1}^M \frac{I_{i,k}}{D_i(w)} \left( \hat{y}_i^{\text{OOB}}(w) - y_i \right) \\ &\quad \times \left( f_k(x_i) - \hat{y}_i^{\text{OOB}}(w) \right) - 2\lambda w_k \end{align}\] Substituting the derivative yields the gradient. \(\blacksquare\)

4 Theoretical Analysis↩︎

4.1 Proof of the L1-Simplex Paradox↩︎

Let the weight vector \(w\) be constrained to the probability simplex \(\Delta^N = \{w \in \mathbb{R}^N : w_j \ge 0, \sum w_j = 1\}\). Under these constraints, the \(L_1\) norm of \(w\) is: \[\|w\|_1 = \sum_{j=1}^N |w_j| = \sum_{j=1}^N w_j = 1\] Because \(\|w\|_1\) is constant across the entire feasible region, its gradient with respect to any active coordinate is zero: \[\nabla_w \|w\|_1 = 0 \quad \forall w \in \text{int}(\Delta^N)\] Thus, adding an \(L_1\) penalty (Lasso) to the objective function has no effect on the optimization path and fails to induce sparsity.

4.2 Concave Penalty Geometry↩︎

SCSB resolves this by employing a concave quadratic penalty \(R(w) = -\|w\|_2^2\). Since the negative \(L_2\) norm is strictly concave, its local and global minima over any compact convex polytope (such as the simplex \(\Delta^N\)) must lie at the extreme points (vertices) of the constraint set.

Theorem 1 (Vertex Convergence of Concave Minimization): Let \(\mathcal{C}\) be a compact convex set, and let \(g(w)\) be a strictly concave function on \(\mathcal{C}\). Then any local minimizer of \(g(w)\) over \(\mathcal{C}\) is an extreme point (vertex) of \(\mathcal{C}\).

Proof: Suppose \(w^* \in \mathcal{C}\) is a local minimizer of \(g(w)\) over \(\mathcal{C}\) but is not an extreme point. Then there exist \(u, v \in \mathcal{C}\) (\(u \ne v\)) and \(\alpha \in (0, 1)\) such that \(w^* = \alpha u + (1 - \alpha) v\). By the definition of strict concavity: \[g(w^*) = g(\alpha u + (1 - \alpha) v) > \alpha g(u) + (1 - \alpha) g(v)\] Without loss of generality, let \(g(u) \le g(v)\). Then: \[g(w^*) > \alpha g(u) + (1 - \alpha) g(u) = g(u)\] This contradicts the assumption that \(w^*\) is a local minimizer, since \(u \in \mathcal{C}\) yields a strictly lower value. Thus, any local minimizer must be an extreme point of \(\mathcal{C}\). \(\blacksquare\)

By combining a convex predictive loss (which pulls the solution into the interior of the simplex to model combinations) with the concave penalty (which pushes weights to the vertices), we create a controllable Pareto frontier. Adjusting \(\lambda\) forces non-essential estimator weights to collapse exactly to 0, achieving true sparsity.

5 Experimental Setup↩︎

We evaluated SCSB across several datasets from scikit-learn and OpenML [13], summarized in Table 1.

• Classification: breast_cancer (binary), diabetes_clf (binary), spambase (binary), and segment (multiclass).

• Regression: diabetes_reg, california_housing, and cpu_act.

3.5pt

5.1 Baselines↩︎

1. Standard Bagging (Uniform): Simple average voting (\(w_j = 1/N\)) [1].

2. Lasso-Pruned Bagging: L1-regularized combination trained on OOB predictions [5].

3. XGBoost: A state-of-the-art gradient boosted tree model (100 trees) [14].

5.2 Base Models↩︎

• Decision Trees: 100 estimators (DecisionTreeClassifier and DecisionTreeRegressor) with bootstrapping.

• Linear Models: 50 estimators (LogisticRegression and Ridge regressors) with bootstrapping.

5.3 Metrics↩︎

Classification models are evaluated using accuracy, Log-Loss, and Expected Calibration Error (ECE) [3]. To maintain evaluation consistency for multi-class paradigms (e.g., segment), we evaluate the multiclass Extension using top-label confidence ECE mapping: \[\text{ECE} = \sum_{m=1}^B \frac{|B_m|}{M} \left| \text{acc}(B_m) - \text{conf}(B_m) \right|\] where \(B\) signifies equally spaced confidence intervals. Regression models are evaluated using Mean Squared Error (MSE) and Coefficient of Determination (\(R^2\)). Inference latency is evaluated in milliseconds per 1,000 predictions (ms / 1k records).

6 Results and Analysis↩︎

6.1 Classification Results↩︎

Table 2 summarizes the classification performance of SCSB and the baseline models.

4.5pt

6.2 Regression Results↩︎

Table 3 summarizes the regression performance of SCSB and the baseline models.

6pt

6.3 Analysis of Results↩︎

As shown in Table 2 and Table 3, SCSB consistently achieves high compression ratios ranging from 33.0% to 96.0%. For example, on the cpu_act dataset using Ridge regressors, it prunes 96.0% of estimators (retaining only 2 out of 50 models) while slightly increasing \(R^2\) to 0.7323 (compared to 0.7293 for standard bagging).

Crucially, Lasso-pruned bagging fails to induce sufficient sparsity on the probability simplex. Because the \(L_1\) norm of weights is constant on the simplex, Lasso-pruned bagging yields 0.0% compression on several configurations (e.g., segment classification and california_housing Ridge regression), retaining all estimators. In contrast, SCSB successfully prunes 74.0% and 80.0% of the estimators on those same configurations.

6.4 Inference Acceleration↩︎

In agreement with our prediction, SCSB’s prediction latency scales linearly with the fraction of active estimators. By completely bypassing zero-weighted base models, SCSB classifiers significantly reduce prediction times. For instance, on the spambase dataset with Logistic Regression, inference time is reduced from 17.33 ms to 3.06 ms (representing a 5.7\(\times\) speedup).

7 Discussion and Future Work↩︎

7.1 Reflection on Findings↩︎

The empirical results confirm that SCSB successfully resolves the trade-off between ensemble accuracy and computational overhead. Minimizing Log-Loss over Out-of-Bag predictions helps calibrate probabilities, which is reflected in low ECE values (e.g., 0.0354 for Breast Cancer Logistic Regression) while reducing ensemble size by 80%. The weight distribution shows a distinct “spike-and-slab” behavior, where a small subset of estimators contains the majority of the ensemble’s representation power, making uniform averaging computationally wasteful.

7.2 Limitations↩︎

• Non-Convexity and Optimization Initialization: The combination of a convex loss function and a strictly concave penalty creates a non-convex optimization landscape. While the SLSQP solver may find local minima, initialization from the uniform prior center (\(w_0 = [1/N, \dots, 1/N]\)) empirically functions as a highly robust initialization anchor, leading to consistent convergence profiles compared against arbitrary randomized simplex origins.

• Training Overhead: Precomputing OOB predictions and solving the simplex optimization adds a post-training phase. Although this is fast (typically under 1 second), scaling it to very large ensembles (\(N > 1000\)) or massive datasets remains a challenge.

7.3 Extensions and Future Work↩︎

The theoretical foundations and empirical success of SCSB open several promising avenues for future investigation:

• Simplex SGD: Developing stochastic gradient descent algorithms on the simplex to scale SCSB to huge ensembles and large datasets.

• Input-Dependent Calibration: Conditioning estimator weights on input features (i.e., \(w_j(x)\)) to perform localized calibration.

• Robustness Across Architectures: Testing SCSB on deep learning ensembles (such as bagged neural networks) and bagged support vector machines (SVMs) to verify its model-agnostic behavior.

8 Conclusion↩︎

Simplex-Constrained Sparse Bagging (SCSB) offers a mathematically rigorous, plug-and-play solution for ensemble compression and calibration. By utilizing Out-of-Bag predictions, SCSB eliminates data leakage without requiring validation splits or cross-validation. We resolve the limitation of Lasso on the probability simplex by employing a concave quadratic penalty. Our experiments demonstrate that SCSB consistently prunes 68%–96% of estimators, providing linear speedups in inference time and superior probability calibration while preserving or enhancing generalization accuracy. This makes SCSB highly suitable for deploying robust bagging ensembles in latency-sensitive production environments.

References↩︎