Subsampled Ensemble Can Improve Generalization Tail Exponentially
Authors: Huajie Qian
Donghao Ying
Henry Lam
Wotao Yin
Venue: NeurIPS 2025 poster ()
Keywords: ensemble method
subsampling
heavy tail
exponential convergence
excess risk
generalization
Primary area: theory
TL;DR: Our paper shows that ensemble learning via majority voting achieves exponentially faster risk decay, improving base learners with slow rates.

Abstract: Ensemble learning is a popular technique to improve the accuracy of machine learning models. It traditionally hinges on the rationale that aggregating multiple weak models can lead to better models with lower variance and hence higher stability, especially for discontinuous base learners. In this paper, we provide a new perspective on ensembling. By selecting the most frequently generated model from the base learner when repeatedly applied to subsamples, we can attain exponentially decaying tails for the excess risk, even if the base learner suffers from slow (i.e., polynomial) decay rates. This tail enhancement power of ensembling applies to base learners that have reasonable predictive power to begin with and is stronger than variance reduction in the sense of exhibiting rate improvement. We demonstrate how our ensemble methods can substantially improve out-of-sample performances in a range of numerical examples involving heavy-tailed data or intrinsically slow rates.

Subsampled Ensemble Can Improve Generalization
Tail Exponentially
Huajie Qian
Donghao Ying IEOR Department UC Berkeley Berkeley, CA 94720 donghaoy@berkelley edu
Henry Lam
DAMO Academy Alibaba Group
IEOR Department Columbia University
Bellevue, WA 98004 h. h. aiiiinaallaaae waamaaalaaaaaaaa inc. com
New York, NY 10027
henry waw.cmlmmmmmblto umbia edu
Wotao Yin
DAMO Academy Alibaba Group Bellevue, WA 98004
wotao hww.oiii@@llbbbbbb inc com
Abstract
Ensemble learning is a popular technique to improve the accuracy of machine learning models. It traditionally hinges the rationale that aggregating multiple weak models can lead to better models with lower variance and hence higher stability, especially for discontinuous base learners. In this paper, we provide a new perspective on ensembling. By selecting the most frequently generated model from the base learner when repeatedly applied subsamples, we can attain exponentially decaying tails for the excess risk, even if the base learner suffers from slow (i.e., polynomial) decay rates. This tail enhancement power of ensembling applies to base learners that have reasonable predictive power to begin with and is stronger than variance reduction in the sense of exhibiting rate improvement. We demonstrate how our ensemble methods can substantially improve out-of-sampa performances in range of numerical examples involving heavy-tailed data or intrinsically slow rates.
Introduction
Ensemble learning 17 65 is a class of methods designed to improve the accuracy of machine learning models by combining multiple models, known as "base learners", through aggregation techniques such as averaging majority voting. In the existing literature, ensemble methods -ost notably bagging [8] and boosting (24] are primarily justified based on their ability reduce bias and variance or improve model stability. This justification has been shown to be particularly relevant for certain U-statistics
and models with thre-thresholding rules, such as decision trees 9 19
In contrast to this traditional understanding, we present a novel perspective on ensemble learning. demonstrating its capability to achieve a significantly stronger effect than variance reduction: By suitably selecting the best base learners trained on random subsamples, ensembling leads to ex- ponentially decaying excess risk tails. Specifically, for general stochastic optimization problems that suffer from slow (polynomial) decay in excess risk tails, ensembling can reduce these tails to an exponential decay rate, substantial improvement beyond the constant-face gains typically exhibited by variance reduction.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To detail our contribution, we consider the generic stochastic optimization problem
min L( := LE' []], DEG
(1)
where 8 E θ is the decision variable, 2 E Z is a random variable governed by some probability distribution, and I(:, is the cost function. A dataset of n i.i.d. samples {=....., =a) is drawn from the underlying distribution of z. In the context of machine learning, 0 corresponds to the model parameters, {z1...., =n) represents the training data, / denotes the loss function, and L. is the population-level expected loss. More generally, (T) also encompasses data-driven decision-man makingg problems, i.c., the integration of data on into a downstream optimization task with overall cost function and prescriptive decision 0. These problems are increasingly prevalent various industrial applications [42 30). For example, in supply chain network design, may represent the decision to open processing facilities, the uncertain supply and demand, and I the total cost of processing and transportation.
Given the data, learning algorithm can be used to map the data to an element in θ, yielding a trained model or decision. This encompasses a variety of methods, including machine learning training algorithms and data-driven approaches such as sample average approximation (SAA) [61 and distributionally robust optimization (DRO) (55) in stochastic optimization. The theoretical framework and methodology proposed in this paper work for all learning algorithms that meet the formal performance criterion in our theorems.
Main Results at a High Level. Let 0 be the output of a learning algorithm. We characterize its generalization performance through the tail probability bound on the excess risk L(Ø) mingge L(0), i.e., (P)) minsee (()) + 6) for some fixed 6 >> O, where the probability is over both the data and training randomness. A polynomially decaying generalization tail refers to:
PP (L())
min L(0) + +6) 2 Cin 8EB
for some a > and C₁ that depends on 5. Such bounds are common under heavy-tailed data distributions 433 40, 41 due to slow concentration, which frequently arises in machine learning
applications such as large language models [39 63 [6], finance [50 31). and physics 22 53). This
can be illustrated with simple linear program (LP):
Example 1.1 (LP with polynomial tail). Consider the stochastic LP minge(o.1) E[ ie., 1(0,2)
=0 and θ = [0, 1] in D. and SAA solution Ô E argminge((o.) Σ z//n Assume = has non- zero density everywhere and is symmetric with respect to its mean E [2] = 1 (hence ( 0). Then we have (0 1) 2 P( z/nn < 0) 2 P( 2 - and Zn < 1 1- n) = P(E nー S
-- 1) (2,, < n), where the last equality uses the independence of 2, By the symmetry of z,
we have P() P( n 1 24 S n - 1) = 1/2, thus for 8 (0, 1) the tail
1 P(= <P(=<1110
TP (.(() BE 10
min I(O) 8) 2 P(O 1)
If has polynomial tail, e.g., P(z < 1- = Q(n for some a > O where 2(-) contains some multiplicative constant, the generalization tail bound (2) applies. Appendix provides another example from linear regression.
As the key contribution of our work, we propose ensemble methods that significantly improve these bounds, achieving an exponentially decaying generalization tail:
P (((()) min L(0) +6) S C2y"//h lE0
where k is the subsample size and < depends on k. 8 with y 0 h: + co. By appropriately choosing i a slower rate in n, the decay becomes exponential. This exponential acceleration is fundamentally different from the well-known variance reduction benefit of ensembling in two perspectives. First, variance reduction refers to the smaller variability in predictions from models trained on independent data sets, thus has more direct impact on the expected regret than the tail decay rate. Second, variance reduction typically yields a constant-factor improvement (e.g., [22 report reduction factor of 3), whereas obtain order-of maggiiiud improvement.

---

Main Intuition. Consider first the discrete space @ Our ensemble method employs a majority-vof mechanism at the model level: The learning algorithm is repeatedly run on subsamples generate multiple models, and the model appearing most frequently is selected as the output. This resembles the majority vote in ensemble methods for classification but the voting is on models instead of classes. This process effectively estimates the mode of the sampling distribution of the learned model by subsampling, and thus is less susceptible to extreme data and training randomness that incurs the slow tail decay in (2). This mode estimation can be formalized via a surrogate optimization problem over the same decision space as ①T) that maximizes the probability of being output by the learning algorithm. The probability objective, the expected value of random indicator function, uniformly bounded even if the original objective is heavy-tailed and hence admits exponential decay in the tail. Consequently, base learners with high-quality mode models receive exponential enhancement in their tail behavior. To illustrate the main idea using Example 1.1 although TP(@ 1) can be substantial in a heavy-tailed setting, it holds that P0 = 0) > TP(O = 1), and thus the mode of 8, i.e. 0, recovers the optimal solution.
For general problems with possibly continuous decision spaces, we replace the majority vote with voting mechanism based on the likelihood of being e e-optimal among all models when evaluated on random subsamples. This avoids the degeneracy of using majority vote for continuous problems while retaining similar (in fact, even stronger) theoretical guarantees. For both discrete and continuous problems, our method fundamentally improves the tail behavior from (2) to
Organization. The rest of the paper is organized as follows. Section 2 presents our methods and their simile- bounds. Section [ presents experimental results, Section discusses related work, and Section (attiionncoom concludes the paper. review of additional related work, technical proofs, and additional experiments can be found in the appendix.
2 Methodology and Theoretical Guarantees
We consider the generic learning algorithm in the form of
A(z knjww: 2" x Ω -
that takes in the training data (zi, Zn) E 2d and outputs model possibly under some algorithmic randomness w E Ω that is independent of the data. Examples of w include gradient sampling in stochastic algorithms and feature/data subsampling in random forests. For convenience, we omit write A(z 2n.) when no confusion arises.
2.1 A Basic Procedure
We first introduce a procedure called MoVE that applies discrete solution or model space θ. MoVE, which is formally described in Algorithm [ repeatedly draws a total of B subsamples from the data without replacement, learns model via A on each subsample, and finally conducts majority vote to output the most frequently subsampled model. Tie-breaking can be done arbitrarily.
Algorithm 1 Majority Vote Ensembling (MoVE)
Input: A base learning algorithm A, i..dd. observations Zi: = (21...., .., 2n), subsample size ko < n. and ensemble size B.
2: for to do
3: Randomly sample 2
= uniformly from Zim without replacement, and obtain
0% 1-=44 A( zk).
4: end for
5: Output: 0, arg maxgee BB 1(0 0g).
To understand MoVE from the lens of mode estimation, we consider optimization associated with the base learner A:
max (0) IP (0- A(zI....,
(5)
PEB
which maximizes the probability of a model being output by the base learner on l: i.i.d. observations. Here the probability P is with respect both the training data and the algorithmic randomness. If
3

---

B = oc, MoVE essentially maximizes an empirical approximation of (5. i...
max OE
P (0 = A(2
(6)
where (si (ai..... 2 is uniform random subsample from (21 2n), and P. denotes the proba- bility with respect to the algorithmic randomness and the subsampling randomness conditioned on (21g...,, 2n). With finite B < oc, extra Monte Carlo noises introduced, leading the following maximization problem
B -10= B
max DEG
2b),,
(7)
6=1
which gives exactly the output of MoVE. other words. MoVE is a bootstrap approximation to the solution of (5). The following result materializes the intuition explained in Section [ on the conversion of the original potentially heavy-tailed problem (T) into a probability maximization that possesses exponential bounds.
Theorem 2.1 (Informal bound for Algorithm D. Consider discrete decision space O Let O == (0 e T(0) S mingree L(f") 8) be the set of 8-optimal models and
max (0) O-6
max Ph (0), #E9/06
where (x( is defined in (5) and max Ps (0) evaluates to 0 i is empty. Then, for every
k S and 8 ssuch that T7,58 > 0, the solution output by MoVE satisfies that
P(L(O,) min ( + 6) S |0| [ <xx((_((n/kb) ( exp(- UEG
(8)
where |0] denotes the cardinality of O and SZ(-) contains multiplicative coefficients that depend on maxéeo Pk (0) and n..b. If 1K,5 > 4/5, (8) is further bounded by
|0| 3mi {o
2225
2/5 ,, max
max Pi(()) max Ps (0)
[0)}}] 0E0//0
+ cg
BEG
where C1, Cz, C3 0 are universal constants.
The formal statement is deferred to Theorem C.7 in Appendix C.2 Theorem 2.1 states that the excess
risk tail of MoVE decays exponentially in the ratio n/k and ensemble size B. The bound
(8) consists
of two terms: The term exp(- (xp(-(((/k)) arises from the bootstrap approximation of (5) with ( whereas the term exp(-S((D) quantifies the Monte Carlo error in approximating (6) with finite B. The multiplier [9] in the bound is avoidable, e.g., via space reduction as in our next algorithm.
The quantity 7 plays two roles. First, it quantifies how suboptimality in the surrogate problem propagates to the original problem (T) in that every T solution for (5) is 8-optimal for Second, 77k., simply means that the mode solution is 6-optimal and hence 7kk, directly quantifies the concentration of the base learner on near-optimal solutions. Therefore, a large T), signals the
situation where the base learner already generalizes well. In this case, (8) reduces to (9). (9) suggests that our approach does not hurt the performance of an already tigh-performing base learner as its generalization power is inherited through the max {1 maxice e Pk(()) (0), max pk (0)) term in the bound. See Appendix B for a more detailed discussion.
Theorem 2.1 also hints the choice of hyperparameterss k and B. As long as TkK5 0, our bound decays exponentially fast, and in this regime the bound ( suggests that a smaller (consequently a larger ratio n/k) leads to thinner tails. However, like other subsampling based ensemble methods (c.g., subagging [2]). reducing the subsample size also enlarges the model bias. In experiments, set k max(10 10, n n/200)) for a balance between tail and bias performance. Regarding the choice of B, we observe from (8) that using a B = (m/kk) is sufficient to control the Monte Carlo error to similar magnitude as the statistical error.
Applying Theorem 2.1 to Example [.] gives an exponential tail as opposed to the slow decay in 33) Corollary 2.2 (Enhanced tail for Example I.I. Consider the stochastic LP in Example ann denote @h: = P(E
* 2, > 0). We have qs > 1/2 by the symmetry of If MoVE is applied to Example 1.1
with A being the SAA, we have maxsse p& (0) 9k. maxge0/e4 P& (0) 1 qk whenever

---

and [+] = 2. Consequently, M6..6 2qk >>>>>>>>> 0 for every k > 0 and 6 < 1, ensuring the tail upper
bound 8) holds. qk > 0.9, we also have the tail upper bound 6 min (c-2/6,C,, -qx)} dz +
2e from 9
The proof of Corollary 2.2 can be found in Appendix C,3
2.2 A More General Procedure
We next present more general procedure called ROVE that applies continuous space where the simple majority vote in MoVE can lead to degeneracy, i.e., all learned models appear exactly once in the pool. Moreover, this general procedure relaxes the dependence on [e] in the bound (8)
Algorithm 2 Retrieval and O-Opimallity Vote Ensembling (ROVE/ ROVEs)
Input: A base learning algorithm A, n i.i.d. observations Zim = (Z1 En), subsample size k1, 42 < (if no split) or n/2 (if split), ensemble sizes B₁ and B2.
Phase I: Model Candidate Retrieval
for = 1 to B, do Randomly sample zk,, (2f,..., = uniformly from Zin (if no split) 21:19J (if split)
without replacement, and obtain 0% A(2f...... end for
Let S == (0% : = ,I. be the set of all retrieved models.
Phase II: c-Optimality Vote
Choose e 2 using the data Zim (if no split) or Z (if split). for b 1 to Bg do Randomly sample zha = (*f...., * uniformly from Zim (if no split) or g1 (if split)
without replacement, and calculate
1 ko
+
b.b kz
S:
Σ
1(0, 2
min E'ES
110' 20 +
12 1=1
==1
end for Output: 0, E arg maXges Ex b= 1
Bg
ROVE, displayed in Algorithm| 2 proceeds initially the same MoVE in repeatedly subsampling data and training the model using A. However, in the aggregation step, instead of using a simple majority vote, ROVE outputs, among all the trained models, the one that has the highest likelihood of being e-optimal. This e-optimality avoids the degeneracy of the majority vote. Moreover, since we have restricted our output the collection of retrieved models, the corresponding likelihood maximization is readily doable by direct enumeration. In addition, it helps reduce competition for votes among best models, as each subsample can now vote for multiple candidates, ensuring a high vote count for each of the top models even when there are many of them. This makes ROVE more effective than MoVE in the case of multiple (near) optima as our experiments will show. We have the following theoretical guarantees for Algorithm 2
Theorem 2.3 (Informal bound for Algorithm 2) Let : zx)) minage L(0)
5) be the excess risk tail of A. Consider Algorithm wiith data splitting, i.e., ROVEs. Let Tx(:): F(supocel(1/)) Σ 1(0, z;) - L(0) > -) be the tail function of the maximum deviation of the empirical objective estimate. Then, for every 5 > O, under mild conditions on e and Tkp (.), it holds that
IP( (T((0)) BEE
min L(0) 25) Bi 3exp( + +exp(-
(10)
+ exp(-S(nnkk)) + exp(- where sl.-) contains multiplicative coefficients depending on (.,(.), 8 and E 8-
Consider Algorithm 2 without data splitting, i.e., ROVE, and discrete space O. Assume limg-soo (8) 0 for all ā > 0. Then, for every fixed > 0, under mild conditions, it holds that lim (()( minsge L(0) + 20) + O.
5

---

The formal statement can be found in Appendix C.4
provides an exponential excess risk tail, regardless of discrete or continuous space. The terms in the square bracket of (TO) are inherited from the bound (9) for MoVE with the majority vote replaced by e-optimality vote. In particular, the multiplier [ 9 is now replaced by B1, the number of retrieved models from Phase I. The last two terms in 10 bound the performance sacrifice due to the restriction to the retrieved models.
Theorem 2.3
ROVE may be carried out with the data split between the two phases, where it referred to ROVEs. Data splitting makes the procedure theoretically more tractable by avoiding inter-dependency between the phases but sacrifices some statistical power by halving the data size. Empirically we find it more effective not to split data.
The optimality threshold is allowed to be chosen in a data-driven way and the main goal guiding this choice is to distinguish models of different qualities. In other words, should be chosen to create enough variability in the likelihood of being 6-optimal across models. In our experiments, we find it a good strategy to choose an that leads to a maximum likelihood around 1/2.
Technical Novelty. Our main theoretical results, Theorems 2.1 and 2.3 are derived using several novel techniques. First, we develop a sharper concentration result for U-statistics with binary kernels, improving upon standard Bernstein-type inequalities (e.g.. 3 57 This refinement ensures the correct order of the bound, particularly (9). which captures the convergence of both the bootstrap approximation and the base learner, offering insights into the robustness of our methods for fast- converging base learners. Second, we perform a sensitivity analysis on the regret for the original problem ① relative the surrogate optimization (5), translating the superior generalization in the surrogate problem into accelerated convergence for the original. Finally, to establish asymptotic consistency for Algorithm wittttt without data splitting, we develop uniform law of large numbers (LLN) for the class of events of being e-optimal, using direct analysis of the second moment of the maximum deviation. Uniform LLNs are particularly challenging here because, unlike fixed function classes in standard settings, this function class dynamically changes with the subsample size k2 as n + co.
3 Numerical Experiments
In this section, we numerically test Algorithm [ (MoVE), Algorithm with (ROVEs) and without (ROVE) data splitting in training machine learning models and solving stochastic programs. Due to space constraints, additional experimental results are provided in Appendix [F] In particular, comprehensive hyperparameter profiling of our algorithms is performed in Appendix F.3 to find empirically well-performing configurations for general use. Unless specified otherwise, all our exper- iments use the recommended configuration summarized at the end of Appendix [3 All experiments
conducted on a personal computer, and Gurobi Optimizer is required for certain experiments stochastic programs. The code is available at:
VoteEnsemble
3.1 Neural Networks and Trees for Regression
Setup. We consider regression problems with multilayer perceptrons (MLPs) and decision trees. Note that classification models are prevalently trained using the cross-entropy loss that is inherently less prone to heavy-tailed noises thanks the presence of the logarithm. For neural networks, the base learner splits the data into training (70%) and validation (30%), and uses Adam to minimize the mean squared error (MSE), with early stopping triggered when the validation improvement falls below 3% between epochs. The architecture of the MLPs is provided in Appendix F.] For trees, the base learner is single regression decision tree with the MSE as the splitting criterion. Besides the base learner, we also compare with three popular tree ensembles, Random Forests (RF) [9, 28). Gradient Boosted Decision Trees (GBDT) (66 27). and XGBoost (XGB) [5 RF are constructed with the same number of trees as our methods for a fair comparison, whereas GBDT and XGB are run with early stopping to avoid overfitting. MoVE is not included in this comparison as it's applicable to discrete problems only.
Synthetic Data. Input-output pairs (X, Y') are generated as Y = (1/50) E log(X, + 1) where each X, is drawn independently from (0, 198(j 1)/49), and the noise is independent of X with zero mean. We consider both standard Gaussian noise and Pareto noise Ei E2, where each E ~ Pareto(2.1). The out-of-sample performance is estimated on

---

common test set of one million samples. Each algorithm is repeatedly applied to 200 independently generated datasets to assess the average and tail performance.
Bike Sharing 21 Superconducciivity [33], and Gas Turbine Emission 11. The data is standardized (zero mean, unit variance). To evaluate the tail probabilities of out-of-sample costs, we permute each dataset 100 times, and each time use the first half for training and the second for testing. Results for three other
Real Data. We use three datasets from the UCI Machine Learning Repository 7
datasets can be found in Figure 13 in Appendix
+
bosed
NOVE
+
HOWES
2464
+
HOVE HOVES
ROVE:
0.7
10P
0.6
Tall prob.
g0 0.44
100
0.3
0.2
21
21
serrole
samole size
Pareto noise, H
(b) Pareto noise, 8.
(c) Pareto noise, 4, 2
Iseve
ROVE
BOVES
baee
ROVE
nOvE
10
0.200
0.175
0.150
taal prob.
50 0.125
0.20
0.100
0.15
0.075
0.10
0.050
0.05
212
212
215
2
2'a
0.62
0.08
0.10
semple size
Semple size
(d) Gaussian noise, 4.
(e) Gaussian noise, H Gaussian noise, 4, 2
Figure 1: Results of neural networks. (e)): Expected out-of-sample costs (MSE) with 95% confidence intervals under different noise distributions and varying numbers hidden layers (H). (c) and (f): Tail probabilities of out-of-sample costs.
ROVES
+
Base
+
ROVE
-4-
ROVES
Bogging
+
Bose
+
ROVE
++-
ROVES -4- Bagging
100
10
18
10F
214
212
2
24
20
25
217
21
2
20
2
212
2
2
sample size
sample size
Sample sioe
(a) Pareto shape 2.1.
(b) Pareto shape 1.5.
(c) Pareto shape 1.1.
Booping
ROVE:
Booping
Bopging
107
10"
10a
(d) Pareto shape = 2.1, 213
(c) Pareto shape 1.5, 213 (f) Pareto shape 1.1, 243
Figure 2: Comparison with bagging in terms of expected out-of-sample costs (MSE) with 95% confidence intervals (a-c) or tail probabilities (d-f) under varying degrees of tail heaviness. Hyperpa-
rameters: k = max(30, n n2/2), K2 = max(30, na.0030,/10000 n/1000), B 50, B₂ 1000.
7

---

10
124
20"
tal prob.
tail prod.
tail proh.
10-1
10
12-4
10
12
10'
157
15
30'
122
127
127
10'
207
10'
CosE
cost
cost
(a) Pareto shape 2.5, n = 2
(b) Pareto shape = 2.0, 2
(c) Pareto shape 1.5, n. = 2
Figure Results of decision trees in terms of tail probabilities of out-of-sample costs (MSE).
Hyperparameters: 1 max (30, n/ 10)) 12 max 2/200, 200), B 50, B2 200.
REVE
ROVER
bass
BOVE
ROVES
10
124
100
tall pr0b.
Eall prob.
tall prob.
2011
20
10
10-2
10"
3005
5500
0000
0100
200
220
2000
200
280
cost
cost
CO9t
(a) Bike Sharing.
(b) Gas Turbine Emission.
(c) Superconductivityy
Figure 4: Results of neural networks with 4 hidden layers three real datasets, in terms of tail probabilities of out-of-sample costs (MSH).
Results. As shown in Figure 1 in heavy-tailed noise settings (Figures la-lc), both ROVE and ROVEs significantly outperform the base algorithm in terms of both expected out-of-sample MSE and tail performance under all sample sizes n. Notably, the performance improvement becomes more pronounced with deeper networks (H 8), indicating that the benefits of ROVE and ROVEs are more apparent in models with higher expressiveness and lower bias.
In light-tailed settings (Figures Id-1f), ROVE and ROVEs show comparable expected out-of-sample performance to the base when H 4, but outperform the base as increases. Additionally, ROVE and ROVEs outperform the base in tail probabilities even when H 4. This indicates that ROVE and ROVEs provide better generalization as the model complexity grows even for light-tailed problems. Similar results for MLPs with 2 and 6 hidden layers can be found in Appendix F.4 where results on least squares regression and Ridge regression are also provided.
Figure 2 shows a comparison with bagging that resembles our method most closely among existing ensemble methods as both involve repeated training on randomly drawn subsamples. We implement bagging, or subagging [12] to be precise. on the MLP with H = 4 hidden layers by averaging the predictions of the repeatedly trained MLPs. The same subsample size and ensemble size are used for our methods and bagging to ensure fair comparison. Whether bagging or our method wins depends on the tail heaviness: ROVE and ROVEs exhibit relatively inferior test performance when the noise has a shape of 2.1, but outperform bagging as the tail of the noise gets heavier towards a shape of 1.1.
Figure 3 demonstrates similar pattern for base learners: ROVE and ROVEs outperform the base learner in all cases, and also outperform RF, GBDT, and XGB especially in high-end tails when the noise gets heavy-tailed with Pareto shape of 1.5. For not heavy-tailed cases, RF, GBDT, and XGB may perform better.
On real datasets (Figure D. ROVE exhibits much lighter tails compared to the base three datasets, and similar tail behavior on the other three. ROVEs, however, underperforms the base in these real-world scenarios, potentially due the data split that compromises its statistical power.
3.2 Stochastic Programs
Setup.
We consider four discrete stochastie programs: resource allocation, supply chain network design, maximum weight matching, and stochastic linear programming, and continuous mean-

---

variance portfolio optimization. All problems are designed to possess heavy-tailed uncertainties. The base learner for all the problems the SAA. Details of the problems are deferred Appendix F2 and results with DRO being the base learner are provided in Appendix F.4
Figure 19
Results. Figure 5 shows that our ensemble methods significantly outperform the base algorithm in all cases except for the linear program case (Figure(5d) Notably, in the linear program case, ROVE and ROVEs still outperform the base, demonstrating their robustness, while MoVE performs slightly worse than the base under small sample sizes. Comparing ROVE and ROVEs, ROVE consistently exhibits superior performance than ROVEs in all cases.
When there is a unique optimal solution, MoVE and ROVE perform similarly, both generally better than ROVEs, as seen in Figures 5a15c However, in cases with multiple optima (Figure 5d). the performance of MoVE deteriorates while ROVE and ROVEs stay strong. This is in accordance with discussion the advantage of e-optimality vote in Section 2.2 Additional results in Appendix F.4 shall further explain that optima multiplicity weakens the base learner for MoVE in the sense of decreasing the 7 and hence inflating the tail bound in Theorem 2.1
The running time comparison in Figure shows that, despite requiring multiple runs on subsamples, our methods do not necessarily incur higher computation cost compared to running base learner on the full sample, and can even advantageous under large sample sizes. This is because, in problems like DRO [5] and two-stage stochastic program, sample- -ased optimization often has problem size that grows at least linearly with the sample size and induces a superlinearly growing computation cost. Subsampled optimizations, computation efficiency of our method is ensured by the fact that no more than O(n/k subsamples needed suggested by the theory and that training subsamples
our approach, are smaller and more manageable. In general, the
be easily parallelized.
Recommended Method. Among the three proposed ensemble methods, ROVE the preferred choice over MoVE and ROVEs for general use as it's applicable to both discrete and continuous problems and consistently delivers superior performance across scenarios.
-
D0VE
ROVE
MOVES
5050
HOVE
ROVES
NoVE
ROVE
- novEs
-3.10
10.5
-13.38
-13.40
Cost
COSE
3.30
17.0
-13.42
16.5
-1.44
-3.25
212
215
225
sample size
sample size
sample
(a) Resource allocation.
Portfolio optimization.
(c) Maximum weight matching.
ROVES
MorE
-13.70
$4.8
-1177
$4.6
mumin time (1)
34.4
-13.0
84.2
-11.8
sample
(d) Linear program (multiple optima).
(c) Network design.
(f) Network design running time.
Figure 5: Results for stochastic programs. (a)-(e): Expected out-of-sample costs with 95% confidence intervals. (f): Running time comparison in the network design problem.
4 Related Work
This work is closely connected to various topics in optimization and machine learning, and we only review the most relevant ones. See Appendix A for additional reviews.
Ensemble Learning. Ensemble learning 17
65 60
improves model performance by combining
multiple weak learners into strong ones. Popular ensemble methods include bagging (8), boosting (24

---

and stacking [62 20). Bagging enhances stability by training models on different bootstrap samples and combining their predictions through majority voting or averaging, effectively reducing variance, especially for unstable learners like decision trees that underpin random forests 11 Subagging [2] is a variant of bagging that constructs the ensemble from subsamples in place of bootstrap samples. Boosting is sequential process where each subsequent model corrects its predecessors'
errors, reducing both bias and variance [37 29]. Prominent boosting methods include AdaBoost
[23] Stochastic Gradient Boosting (SGB) 126 27, and Extreme Gradient Boosting (XGB) [25] which differ in their approaches to weighting training data and hypotheses. Instead of using simple aggregation like weighted averaging or majority voting, stacking trains a model to combine base predictions to further improve performance. A key procedural difference of our approach from these methods is that we perform majority voting at the model rather than prediction level to select single best model from the ensemble. That is, our approach outputs models in the same space as the base learner, whereas existing ensemble methods yield aggregated models outside the base space. This also means a constant inference cost for our output model with respect to the ensemble size, as opposed linearly growing costs seen in existing ensemble methods. Methodologically, our approach operates by accelerating excess risk tail convergence in lieu of bias/variance reduction, and hence is particularly effective in settings with heavy-tailed noise.
Optimization and Learning with Heavy Tails. Optimization with heavy-tailed noises has garnered significant attention due to its relevance in traditional fields such as portfolio management [50] and
scheduling [3]. as well as emerging domains like large language models [0] 2]. Tail bounds of
most existing algorithms are guaranteed to decay exponentially under sub- Gaussian or uniformly bounded costs but deteriorate to a slow polynomial decay under heavy-tailedness
45
(6]
For SAA or ERM, faster rates possible under the small-ball 52 51 59 or Bernstein's 's condition
[8] on the function class, while our approach is free from such conditions. Considerable effort has been made mitigate the adverse effects of heavy-tailedness with robust procedures among which (MOM) [47 approach is most similar to ours. The basic idea there is to estimate a true mean by dividing the data into disjoint subsamples. computing an estimate on each, and then taking the median. 45 48 46 4
the geometric median [54), or more generally, meddinn-of-meet
use MOM in estimating the expected cost and establish exponential tail bounds for the mean squared loss and convex function classes. [36 35 apply MOM directly on the solution level for continuous problems and require strong convexity from the cost to establish generalization bounds. Besides MOM, another approach estimates the expected cost via truncation [14] and allows heavy tails for linear regression 4 64 or problems with uniformly bounded function classes [1] but computationally intractable due to the truncation and thus more of theoretical interest. In contrast, our ensemble approach is
a meta algorithm that provides exponential tails as long as the base learning algorithm possesses reasonble predictive performance as characterized in our Theorem 2.1 Relatedly, various techniques such as gradient clipping [66 K2) and MOM (58) have been adopted in stochastic gradient descent (SGD) algorithms to handle heavy-tailed noises, but their focus is the faster convergence of SGD rather than generalization.
5 Conclusion and Limitations
This paper introduces novel ensemble technique that significantly improves generalization by estimating the mode of the sampling distribution of the base learner via subsampling. In particular, our approach converts polynomially decaying generalization tails into exponential decay, thus providing order-of-magniudd improvements as opposed to constant factor improvements exhibited by variance reduction. Extensive numerical experiments in both machine learning and stochastic programming validate its effectiveness, especially for scenarios with heavy-tailed data and slow convergence rates. This work underscores the powerful potential of our new ensemble approach across broad range of machine learning applications.
Regarding limitation, our method may increase model bias like other subsampling-bass techniques such as subagging [12. making it best suited for applications with relatively low bias, e.g., when the base learner is sufficiently expressive. Moreover, the tail guarantee of our method requires the mode of the sampling distribution of the base learner to be a reasonably good model.
10

---

References
[1] Gas Turbine CO and NOx Emission Data Set. UCI Machine Learning Repository, 2019. DOI: http:///cb.org11022422/CCC
[2] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arX1v:2303..08774 2023.
[3] Miguel A Arcones. A bernstein-ttyp inequality for u-statistics and u-processes. Statistics & probability letters, 22(3):239-247, 1995.
[4] Jean-Yves Audibert and Olivier Catoni. Robust linear least squares regression. The Annals of Statistics, (9(5):7766-2777 2011.
[5] Aharon Ben-Tal, Dick Den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 39(2):341337,, 2013.
[6] Dimitris Bertsimas, Shimrit Shtern, and Bradley Sturt. A data approach to multistage stochastic linear optimization. Management Science, 69(1):51-74, 2023.
[7] Catherine L Blake. Uci repository of machine learning databases. http://www. ics, uci. edu/" mlearn/MLRepositor html, 1998.
[8] Leo Breiman. Bagging predictors. Machine learning. 24:123-144 1996.
[9] Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
[10] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[11] Christian Brownlees, Edouard Joly, and Gábor Lugosi. Empirical risk minimization for heavy- tailed losses. The Annals of Statistics, 43(6):2507-2534 2015.
[12] Peter Bühlmann and Bin Yu. Analyzing bagging. The Annals of Statistics, 30(4):927-961, 2002.
[13] Andreas Buja and Werner Stuetzle. Observations on bagging. Statistica Sinica, pages 323-351, 2006.
[14] Olivier Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de I'IHP Probabilités et statistiques, 48(4): 148-118811111 1185, 2012.
[15] Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
[16] Ashok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic opti- mization with heavy tails. Advances in Neural Information Processing Systems, 34:4883-4895. 2021.
[17] Thomas G Dietterich. Ensemble methods in machine learning. In International workshop on multiple classifier systems, pages 1-15, Springer, 2000.
[18] Vu C Dinh, Lam Ho, Binh Nguyen, and Duy Nguyen. Fast learning rates with heavy-tailed losses. Advances in neural information processing systems, 29, 2016.
[19] Harris Drucker and Corinna Cortes. Boosting decision trees. Advances in neural information processing systems, 8, 1995.
[20] Saso Džeroski and Bernard Zenko. combining classifiers with stacking better than selecting the best onc? Machine learning. 54:255-273. 2004.

---

[21] Hadi Fanaee-T. Bike Sharing. https//dbb..org/10.4444/////
UCI Machine
Learning Repository, 2013.
DOI:
[22] Yves Fortin and Maxime Clusel. Applications of extreme value statistics in physics.
Journal of Physics A: Mathematical and Theoretical, 48(18): 2015.
[23] Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of machine learning research, 4(Nov):933-965 2003.
[24] Yoav Freund, Robert E Schapire, et al. Experiments with a new boosting algorithm. In icml, volume 96, pages 148-156 Citeseer, 1996.
[25] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: A statistical view of boosting (with discussion and a rejoinder by the authors). The Annals of Statistics, 28(2):337-405 40777747,422 2000.
[26] Jerome H Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5): 1
2001.
[27] Jerome H Friedman. Stochastic gradient boosting. Computational statistics & data analysis, 38(4):367-378, 2002.
(28) Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63(1):3-42, 2006.
[29] Indrayudh Ghosal and Giles Hooker. Boosting random forests to reduce bias; one-step boosted forest and its variance estimate. Journal of Computational and Graphical Statistics, 30(2):493- 502, 2020.
[30] Shubhechyya Ghosal, Chin Pang Ho, and Wolfram Wiesemann. A unifying framework for the capacitated vehicle routing problem under risk and ambiguity. Operations Research, 72(2):425- 443, 2024.
[31] Manfred Gilli and Evis Këllezi. An application of extreme value theory for measuring financial risk. Computational Economics, 27:207-228, 2006.
[32] Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy-tailed noise via accelerated gradient clipping, Advances in Neural Information Processing Systems, 33:15042-15053, 2020.
[33] Kam Hamidieh. Superconductivty Data. UCI Machine Learning Repository, 2018. DOL:
[34] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301): 1963.
[35] Daniel Hsu and Sivan Sabato. Heavy-tailed regression with a generalized median-of-means. In International Conference on Machine Learning, pages 37-45. PMLR, 2014.
[36] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1-40, 2016.
[37] Bulat Ibragimov and Gleb Gusev. Minimal variance sampling in stochastic gradient boosting. Advances Neural Information Processing Systems, 32, 2019.
[38] Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Stochastic scheduling heavy-tailed jobs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Baatoss-Dagstuhll-aae
Zentrum für Informatik, 2015.
[39] Hamid Jalalzai, Pierre Colombo, Chloé Clavel, Eric Gaussier, Giovanna Varni, Emmanuel Vignon, and Anne Sabourin. Heavy-tailed representations, text polarity classification & data augmentation. Advances Neural Information Processing Systems, 93:4795-4307, 2020.
[40] Jie Jiang, Zhiping Chen, and Xinmin Yang. Rates of convergence of sample average approxima- tion under heavy tailed distributions. To preprint Optimization Online, 2020.
12

---

[41] Jie Jiang and Shengjie Li. On complexity of multistage stochastic programs under heavy tailed distributions. Operations Research Letters, 49(2):265-269, 2021.
[42] Sachin S Kamble, Angappa Gunasekaran, and Shradha A Gawankar. Achieving sustainable performance in data-driven agriculture supply chain: A review for research and applications. International Journal of Production Economics, 219:179-194, 2020.
[43] Vlasta Kañková and Michal Houda. Thin and heavy tails in stochastic programming. Kyber- netika, 51(3):433-45,, 2015.
[44] Joon Kwon, Guillaume Lecué, and Matthieu Lerasle. A mom-based ensemble method for robustness, subsampling and hyperparameter tuning. Electronic Journal of Statistics, 1201) 1227, 2021.
[45] Guillaume Lecué and Matthieu Lerasle. Learning from mom's principles: Le cam's approach. Stochastic Processes and their applications, 129(1 1):4385-4410, 2019.
[46] Guillaume Lecué and Matthieu Lerasle. Robust machine learning by ceddian-of-mennn Theory and practice. The Annals of Statistics, 48(2):906 2020.
[47] Gábor Lugosi and Shahar Mendelson. Mean estimation and regression under heavy-tailed distributions: A survey, Foundations of Computational Mathematics, 19(5):1145-1199) 2019.
[48] Gabor Lugosi and Shahar Mendelson. Risk minimization by median-of-men tournaments. Journal of the European Mathematical Society, 22(3):925-965 2019.
[49] Gábor Lugosi and Shahar Mendelson. Sub-Gaussian estimators of the mean of random vector. The Annals of Statistics, 47(2):783-794, 2019.
[50] Georg Mainik, Georgi Mitov, and Ludger Rüschendorf. Portfolio optimization for heavy-tailed assets: Extreme risk index vs. markowitz. Journal of Empirical Finance, 32:115-134, 2015.
[51] Shahar Mendelson. Learning without concentration. Journal of the ACM (JACM), 62(3):1-25, 2015.
[52] Shahar Mendelson. Learning without concentration for general loss functions. Probability T'heory and Related Fields, 171(1):499-50) 2018.
[53] Anna PM Michel and Alan D Chave. Analysis of laser-induced breakdown spectroscopy spectra: the case for extreme value statisties. Spectrochimica Acta Part B: Atomic Spectroscopy, 62(11):1370-137) 2007.
[54] Stanislav Minsker. Geometric median and robust estimation in banach spaces. Bernoulli, 21(4):2308-238 -2333, 2015.
[55] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the wasserstein metrie: Performance guarantees and tractable reformulations. Mathemati- cal Programming. 11)::115-1666 2018.
[56] Roberto Oliveira and Philip Thompson. Sample average approximation with heavier tails
i: non-asymptotic bounds with weak assumptions and stochastic constraints. Mathematical Programminng 199(1):1-48, 2023.
[57] Thomas Peel, Sandrine Anthoine, and Liva Ralaivola. Empiriaal bernstein inequalities for u-statistics. Advances in Neural Information Processing Systems, 23, 2010.
[58] Nikita Puchkin, Eduard Gorbunov, Nickolay Kutuzov, and Alexander Gasnikov. Breaking the heavy-tailed noise barrier in stochastic optimization problems. In International Conference Artificial Intelligence and Statistics, pages 856-864. PMLR, 2024.
[59] Abhishek Roy, Krishnakumar Balasubramanian, and Murat A Erdogdu. On empirical risk minimization with dependent and heavy-tailed data. Advances Neural Information Processing Systems, 34:8913-899 8926, 2021.
13

---

[60] Omer Sagi and Lior Rokach. Ensemble learning: A survey. Wiley interdisciplinary reviews: data mining and knowledge discovery, 1(4): 2018.
[61] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszezynski. Lectures on stochastic programming: modeling and theory. SIAM, 2021.
[62] David H Wolpert. Stacked generalization. Neural networks, 5(2):241-255) 1992.
[63] Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15393, 2020.
[64] Lijun Zhang and Zhi-Hua Zhou. fe-ressessoon with heavy-tailed distributions. Advances in Neural Information Processing Systems, 31, 2018.
[65] Zhi-Hua Zhou Ensemble methods: foundations and algorithms. CRC press, 2012.
14

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The major claim made in our paper that we proposed a new ensemble learning method that attains exponentially decaying tail for excess risk. This claim is theoretically proved in Section 2 Moreover, we have conducted extensive numerical experiments in Section 3 to support theoretical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations of our work in Section S
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
15

---

Answer: [Yes]
Justification: We clearly stated the assumptions/condtions required for each theoretical results. Proofs of the results are documented in Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proof' in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: All our figures are reproducible, and the codes for the experiments are dis- closed.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
16

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provided the codes for reproducing our experiments. No data is needed for our paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
aublicc/uudees/Codeuubbss wtw.eeeewuumiisioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttps/cccppplcccuui.eeeeeecccuea
witeeee//ooSSSeSeS...ee.a www.ssssiicggooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The problem instances used in the experiments can be found in our disclosed code. The experiment methodologies are clearly stated in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We repeated each our experiments for more than 50 times, reporting both the average performance and the standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: As stated at the beginning of Section our experiments are performed a personal computer, and Gurobi Optimizer is required for reproducing some of experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the wttpppsscccppppccccecccpcc httpppbiitttthiiicccdeeieeeeee
NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our paper theoretical work studying ensemble learning and stochastic optimization, and it does not have any ethical issue.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper theoretical work studying ensemble learning and stochastic optimization, and it does not have societal impact concerns.
18

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper is a theoretical work studying ensemble learning and stochastic optimization, and it does not pose such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The Gurobi academic license is used for our numerical experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssippsssie thcode wwwccom/aaaoo//c datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper is theoretical work studying ensemble learning and stochastic optimization, and we do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper is theoretical work studying ensemble learning and stochastic optimization, and does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper is a thcoretical work studying ensemble learning and stochastic optimization, and it does not incur such risks.
Guidelines:
20

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are only used polish the writings of some sentences in our paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy dbtppss/eaarrrps..c//oofffeeeee for what should or should not be described.
21

---

Supplemental Materials
The appendices are organized as follows. In Appendix A we review additional related work. Appendix B presents additional technical discussion for Theorem 2.1 Next, in Appendix C we document the proofs of the main theoretical results in our paper. Specifically, we introduce some preliminary definitions and lemmas in Appendix C.1 Then, the formal statement and the proof of Theorem 2.1 can be found in Appendix C.2 The proof of Corollary [.2 is in Appendix C.3 The formal statement and the proof of Theorem 2.3 can be found in Appendix C.4 To improve
clarity, we defer the proofs for all technical lemmas to Appendix [D] In Appendix E we provide
another motivating example that supplements Example 1.1 Finally, we provide additional numerical experiments in Appendix F
A Additional Related Work
Bagging for Stochastic Optimization. Bagging has been adopted in stochastic optimization for various purposes. The most relevant line of works 770 90, 95 71 study mixed integer reformu- lations for stochastic optimization with bagging approximated objectives such as random forests and ensembles of neural networks with the ReLU activation. These works focus on computational tractability instead of generalization performance. [66] empirically evaluates several statistical techniques including bagging against the plain SAA and finds bagging advantageous for portfolio optimization problems. [72] investigates a batch mean approach for continuous optimization that creates subsamples by dividing the data set into non- -verraaaag batches instead of resampling and aggregates SAA solutions on the subsamples via averaging, which is empirically demonstrated to reduce solution errors for constrained and high-dimensional problems. Another related batch of works 88 88 78 77 81 concern the use of bagging for constructing confidence bounds for generalization errors of data-driven solutions, but they do not attempt to improve generalization. Related to bagging, bootstrap has been utilized to quantify algorithmic uncertainties for randomized algorithms such as randomized least-squares algorithms [89), randomized Newton methods (74), and stochastic gradient descent 82 97]. which is orthogonal to our focus on generalization performance.
Machine Learning for Optimization. Learning to optimize (L20) studies the use of machine learning in accelerating existing or discovering novel optimization algorithms. Much effort has been in training models via supervised or reinforcement learning make critical algorithmic decisions such as cut selection (e.g., 80 94] search strategies (e.g.. [85] 84, 91],, scaling [69], and primal heuristics [Р3] in mixed-integer optimization, even directly generate high-quality solutions (e.g.. neural combinatorial optimization pioneered by (67)). See [75 76 68 996 for comprehensive surveys on L20. This line of research is orthogonal our goal, and L20 techniques can work as part of or directly serve as the base learning algorithm within our framework.
B Implications of Theorem 2.1 for Strong Base Learners
We provide a brief discussion of Theorem 2.1 applied to fast convergent base learners. Based on Theorem 2.1 the way maxage (f) and max (f) enter into (9) reflects how the generalization performance of the base learning algorithm is inherited by our framework. To explain, large maxege (0) and small maxøge/e4 (a(()) correspond to better generalization of the base learning algorithm. This can be exploited by the bound (9) with the presence of max (1 maxage (v((), max /e= (t)) which is captured with our sharper concentration of U-statistics with binary kernels. In particular, for base learning algorithms with fast generalization
convergence, say 1 maxace Pk (0) O and max (o) O(e O(e=*) for simplicity, we have C3 max {1 maxøee P& (0), max (+)) O(e and hence the first term in (9)
becomes (e-") which matches the error of the base learning algorithm applied directly to the full data set.
22

---

C Proofs for Main Theoretical Results
C.1 Preliminaries
An important tool in the development of our theories is the U-statistic that naturally arises in subsam- pling without replacement. We first present the definition of U-statistic below and its concentration properties in Lemma C.2 The proof of Lemma C.2 can be found in Appendix D.1
Definition C.1. Given the i.i.d. data set {21, (21,.... ..., Fn) C and (not necessarily symmetric) kernel of order & I n is function & : g - such that [1<(21..... =x oo, the U-statistic associated with the kernel K is
U (I, (n 1) (n k + 1gh, Sa s.t. ii ViSa<iŞk
Σ
((2 Pig.)
Lemma C.2 (MGF dominance of U-statistics from 34).. For any integer O < k S n and any kernel
n(2,,...,, 2k), let ( be the corresponding U-statistic defined in Definition C.I and
Ln/k]
R(21,..., 2n)
16 1((2(t :.aft-
(11)
[n/k]]
be the average of the kernel across the first |n/k data. Then, for every RR it holds that [exp(tU)) S B [exp(tR)).
E
Next, present sharper concentration bound for U-statistics with binary kernels. The proof of Lemma C.3
can be found in Appendix D.2
Lemma C.3 (Concentration bound for U-statistics with binary kemnlls). Let 1o(21.... 2k; w) be {0, (..1)-wen v-valud kernel of order k S that possibly depends additional randomness w that independent of the data (nn) x² (21...., Fx)) == [.( 2 (Z).... 2k], and UZ1....., 2n) be the U-statistic associated with k". Then, it holds that
(U [x] 2 e) exp
(-
n
DKL (E [x] E [+])
2k
n DKL (E - e (n))
PP (U E [K] < -)) exp
2k
where DKL (pllg) == pln : (1 in 1 the KL-divergence between two Bernoulli random variables with parameters p and q, respectively.
Below, Lemma C.4 givies lower bounds for KI. divergences which help analyze the bounds in Lemma The proof of Lemma C.4 deferred to Appendix [D.
Lemma C.4. Let (KL(pllq) == pl & + (1-p) In + be the KL-divergence between two Bernoulli random variables with parameters and q, respectively. Then, it holds that
DKL(pllg) pln
P + p.
(12)
9
pf E (1, for some y E (0, }11 it also holds that
(kt(pllg) 2 (2(g(1 (2(g(1-9)) -)))).
(13)
To incorporate all the proposed algorithms in a unified theoretical framework, we consider a set-valued mapping
A( A(z1....=x:w) 2 Ω 2
(14)
where Ω denotes algorithmic randomness that is independent of the data {21, ......., 2k E Each of our proposed algorithms attempts to solve the
2
problem
max (0) : P. (0 A(2i..... ...,, 2;: IE0
(15)
for a certain choice of A, where . =t} } is subsampled from the i.i.d. data { 2n)
uniformly without replacement, and P.. denotes the probability with respect the algorithmic
23

---

randomness w and the subsampling randomness conditioned on the data. Note that this problem is an empirical approximation of the problem
max P=(() :- P (0 E A(zI.... ,.iw))
(16)
The problem actually solved with finite number of subsamples is
max (0) AE0
B Σ 1(0 A(z)..... ... =R::w)))
(17)
Specifically, Algorithm T
uses
, -b; (A(zi w))
(18)
where A denotes the base learning algorithm, and Algorithm 2 uses
A(zi
w) 0 S:
1(0,
min (0++)) C'ES
(19)
K2 1=1
==1
conditioned on the solution set retrieved in Phase I. Note that no algorithmic randomness is involved in (19) once the set S is given. Now, we introduce the following definitions.
Definition C.5. For any E [0. 1]. let
P {0 O (0) 2 max (0') 8}
(20)
Pree
be the set of 5-optimal solutions of problem (16 Let
m
arg max pk (a. 6ce
be a solution with maximum probability that is chosen in a unique manner if there are multiple such solutions. Let
P = {0 θ pu (0) 2 Pa (0max
8}
(21)
be the set of 8-optimal solutions relative to 0 for problem 15 Definition C.6. Let
0 = o L()) < min L + +8
(22)
d'ee
be the set of d-optimal solutions of problem solutions. Let
In particular, @ represents the set of optimal
k min Σ 110', 2:) + G = 0 e :: k Σ 100
k
(23)
d'ee k
1=1
be the set of 8-optimal solutions of the SAA with i.i.d. data .E,,...,kk)
C.2 Proof of Theorem 2.1
Theorem C.7 (Formal finite-sample bound for Algorithm D.. Consider discrete decision space θ. Let pmax = maxége pa (0), where (0) is defined in (5). and
T8k,5 : Pk max
max P0)
(24)
8
where max (b) evaluates to 0 e is empty. Then, for every k S and 2 0 such that
n > 0, the solution output by MoVE satisfies that
P
L(O.)
min L( +6 DE0
< -10
exp
n 2k
DRL.
PE
3mp..5
11..8 Pt
2 eex
(-
DKL.
(Pé
max
70.55
pt
2k:
4
B
n2.
exp
24
min
31p
8/4
+1
7kk.6
< 1)
eep
DKL
pk
77.55
pk
B
n
4
2k
24
max
TJk
(25)

---

In particular. if 1k.6 > 4/5. (25) is further bounded by
}}
222
2/5 C1 max [ 3 m
1-
Pk
max
pv Pb(0) 8E9/8/
max
+
B/Cs
(26)
where C₁ C22 C3 > O are universal constants, 19) denotes the cardinality of O and DRt. (pll))
p In P. + (1 p) 1 is the Kullback-Leeie divergence between two Bernoulli distributions with q means p and
We consider Algorithm 3 generalization of Algorithm applied to the set- valuvalued learning algorithm in (14). This framework recovers Algorithm D as special case under condition (18). Again, we omit the algorithmic randomness in A for convenience. For Algorithm simite-sample guarantee.
we derive the following
Algorithm 3 Majority Vote Ensembling for Set- Valued Learning Algorithms
1: Input: A set-valued learning algorithm A, i.idd observations Zi:n = (21,..., 2n), positive integers & < n, and ensemble size B.
2: for b == to B do
3: Randomly sample z (ef....., >)) uniformly from Zim without replacement, and obtain
@ (= A 2
4: end for
5: Output 0, E arg pee E 1(0 E (.)
Theorem C.8 (Finite-sample bound for Algorithm 3 Consider discrete decision space +. Let
Pk max maxage pie (0), where (0) defined in 16). For any denote
16k,5 = Pk max
max (0), 8
(27)
where max (0) evaluates to O @ is empty. Then, for every and such that
Th > O, the solution output by Algorithm 3 satisfies that
I(Om))
min ((O) BE0
+
$ |
exp
11 2k
DKL.
Pk
max
37
pk
max
17 )) + 2-2exxp
(-
11
-KI.
Pkk
max
$
2
max
4
2k
B
1/2
+ exp
24
min {pmax 1 - pluax + 3n/4/
+ plaa
17
exp (
12
DKL (pitax +
17
Pk
max
B
77
2k
24
Pk
max
+
n/4
(28)
for every E (0, T.. In particular, if Tk.6 > 4/5, 15,00 28
is further bounded by
|0| 3 e 2/5 6-2/5,C. max { 1 11-Ph
pa(00)]
cak
B (-Ca)
max
max
texp
(29)
e
where C₁, C2 C3 > are universal constants, and DKL (pllg) == pln P + (1 p) In 1-p
the
i-g
Kullback-Leiblrrdde divergence between two Bernoulli distributions with means p and q.
Proof of Theorem
C.8
We first prove excess risk tail bounds for the problem (16), split into two
lemmas, Lemmas
and C.10 The proofs for these two lemmas can be found Appendix
and Appendix
D.5
respectively.
Lemma C.9. Consider discrete decision space Q. Recall from Definition C.5 that pk max holds for Omax, For every 0 S < < yaaxx it holds that
(P% 2 P
& |
exp
n
DKL
Pk
max
+
pk
max
2k
2
8
+ exp
DKL
Pk
max
Pk
max
2k
25

---

Lemma C.10. Consider discrete decision space Q For every e [0, 1] it holds for the solution output by Algorithm Itht
Ps On S101 (-6 min {px (Onax) Du (O +e)
B
where |-| denotes the cardinality of a set and P. denotes the probability with respect to both the resampling randomness conditioned the observations and the algorithmic randomness.
We are now ready for the proof of Theorem C.8 We first note that, if T O, it follows from Definition C.5Ithat that
Pk C O for any 7 (0, m).a))
Therefore, for any E (0, (), we can write that
P (6, 0*) s (n $ PK)
s P (( PP/2] u p & p?})
(30)
P (0n & pp + (P g PD)
We first evaluate the second probability on the right-hand side of (30). Lemma C.9 gives that
(PM g PP) s |
cxp
DKL
Pk
max
31
Pk
max
17
2k
4
(31)
+ exp
(-
n
-KLL
Pk
max
-
max
2k
Next, by applying Lemma C.10 side of (30) as
with
n1/2, we can bound the first probability on the right-hand
P On pm12)
10 exp
24 min (px(0 ). Pr. (0 + 1/22
B
1/2
(32)
Conditioned on the value of Pa. (Omuax, we can further upper-bound the right-hand side of 32 as follows
B
7
E
exp
24
min (px(Or
Pk (A (Amax)) }} + 11/2//
< IP
Pa (Omaxx
I pk
max
2) exp
B
1/2
+
24 phax + 17/4
B
1/2
IP
D& (fmax)
Pk
max
<
4 exp
24
min fpr 1 - Pk
mmx } + 37/4
+
B
112
IP Pa (Amax)
2 Pk
max
4
exp
24
P max + n/4
IP
Pa (0
Pk
max
7)
11)
cxp
24
B
min fymaa
1/2
pmmaa] + 3n/4 ) +
IP
Pk (Omaax
2 Pk
max
)
exp
B
11²
24
mmx + 7/44
exp
n
DKL.
Pk
max
+
2k
4
B
1j2
exp
24
min {pmmax 1
pmaaa + 31/4
+
Pk
max
7)
<
.exp (-
(-
71
DKL.
(p
max
17 max
Ph
exp
B
1/²
4
23
24
P
max
+ 4/
26

---

where inequality (?) results from applying Lemma Pk max Together. the above equations imply that
C.3 with P& (6 the U-statistic estimate for
P 0n & (6)
3n
s |0]
exp
DKL
Pk
max
Pkc
max
2k
+2 exp
(-
n
DKL
Pkk
!?
pitaas
2k
4
B
112
+ cxp
24
min
{phiax
- } + 377/4)
+1
Pk
max
+
17
exp
n DRI. max
Pk
+
17 max
Pk
2k
plax + 17
Since the above probability bound is left-continuous in and can be arbitrarily chosen from (0, 5), 6), the validity of the case 17 = 7k..5 follows from pushing 17 the limit 17,.6. This gives (28)
To simplify the bound in the case 7k.5 > 4/5. Consider the bound (28) with 7j = 7k. Since Pk 2 8 by the definition of f...5. s. must hold that pxux - - > 1/5+1/5
therefore the last term the finite-sample bound 28 vanishes. To simplify the first two terms in the finite-sample bound, we note that
3
4
Pk max
3
5'
31Tk.8
3
Pk
max
2
4
4
5'
T7K.6
4
Pk
max
<
1
4
4
5
5'
Tik.5
3
Pk
max
4
2
7k.88
5
and that Ph max T S the first two terms as
T S 1/5, therefore by the bound
[13
from Lemma C.4
we can bound
exp
n
DRL.
Pk
max
31)k,6
Pk
max
2k:
4
exp
T2
In
(2((P)
max
- -),,,)
1x + -Tx, (1)1)/1)) 1/6))
2h:
2((p max T7,,6) pkaxx + (Tx,)) m/(22)
2(ppaxx )/66) n/(26)
(2 T)) n/(1OR)
and similarly
exp (- 2k
DRL.
Pk
max
max) ))
5
exp
n2 In 22(p (1 pk 1)2/3)))/
4
2k
p )//5 (2(22))
2(phaax
pk max / n2(2k)
< (2(1
(2 pk maxx n0(1OR))
On the other hand, by Lemma C.4 both DKL. (ymaa
3rJk, / 11pp T).
and
DKL (p T/..8/ / max) are bounded below by // therefore
exp (- n
DKL Pk max
3rm 8
Pk
max
71,,6 ))
S exp
n
Thes
< exp
(- n
2k
4
2k
8
25k
27

---

M/,,6/ //4,6/41pp //))) For the third term in the bound and the same holds for exp (-n/(2k)- DKL (px we have
28
(4/5)2
16
min (Uk
max
Pk maxx
+ 8//
min (1,1/5} + +3/4
25"
and hence
B
Th.s
B
exp
exp
24
min {pk max
Pk max 3
75/2
The first desired bound then follows by setting Ci, C2 C3 to be the appropriate constants. completes the proof of Theorem C.8
This
Proof of Theorem
Algorithm Dis a special case of Algorithm with the learning algorithm (18
that outputs a singleton, therefore the results of Theorem C.8 automatically apply. In particular,
M = 5 in the context of Theorem C.7 and (55 follows from setting v to be 77, in
C.3 Proof of Corollary 2.2
Proof of Corollary 2.2 By the continuity and symmetry of z we have q = k)
F(E 1= 24 E (0, k)) = 1/2 P 2 E k)).)). Since z has a non-zero density everywhere,
P(E 2 E k)) 0, thus 9k 1/2 for every it
We note that the SAA of the linear program outputs either 0 or 1, therefore the space [0, 1] can be effectively viewed as the binary set {0, 13 and Theorem 2.1 is applicable with | 2. To apply Theorem 2.1 it can easily seen that
maxxee Pk (0) P0 = 0) = qs and that maxpges P& (0) = P(O = = 1- qk for å < 1. This gives T7k.6 2qk 1 0. Therefore the bound (8) holds for every k > and 8 <<1, If gk 0.9.
we have 5 > 4/5, and hence the bound (10) holds. The particular form of the bound (10) is then
obtained by plugging in the values for maxage py: (0), maxgee/e (f) and |0).
C.4 Proof of Theorem
Theorem C.11 (Formal finite-saple bound for Algorithm 2. Let Ex,5 = P(L(A(21,.... .x.....,,,))),)). > mingee L(0) + 8) be the excess risk tail of A. Consider Algorithm 2 with data splitting, i.e. ROVEs. Let Tx(-) = PP(supecel(1 /k) E 1(0, 24) T.(0) .) be the tail function of the maximum deviation of the empirical objective estimate. For every > 0, if is chosen such that P( E [c) for some 0 < < < and Tky ((5 7)/2) 3)= Tk2 (c/2) < 1/5, then
3 min {
min {s, E}
2022
((.((.)) > min I.(0) 26) <B
2/5 k 2/5
6 B2/Ca
REB
+ min { (1 (1-E,,))/a CBEng
20 te B1 (1(1-E4 s)/
(33)
where C1, C2. C3 are the same as those in Theorem C.7 and C4, Cs Co, Or are universal constants.
Consider Algorithm 2 without data splitting, iee. ROVE, and discrete space O. Assume
lim (8) 0 for all > 0. Then, for every fixed 8 > 0. we have lim P(L(Ôn) >
mingee L(0) 26)
O, if lim sup En, < 1. IP (e > 8/2) + O. kı and loz + o0.
ni/ki and n/k2 + oo, and B1, B2 + as oc.
We first present two lemmas to be used in the main proof. The following Lemma C.12 characterizes the exponentially improving quality of the solution set retrieved in Phase where its proof can be found in Appendix D.6
Lemma C.12 (Quality of retrieved solutions in Algorithm
2. For every and 8 2 O, the set of k and without data splitting satisfies that
retrieved solutions S from Phase I of Algorithm 2 with h
P P =0) < min -1 W1C CsEK,8
J5 + exp
BB (-
((a-EE.))
(34)
where C4. Cs, Co, Cr are universal constants. The same bound with n. replaced by n/2 holds true for Algorithm 2 with data splitting.
28

---

Then, Lemma C.13 gives bounds for the excess risk sensitivity f,,.5 in the case of the set-valued
learning algorithm 19 The proof of Lemma C.13 can be found in Appendix
Lemma C.13 (Bounds of i for the set-valued learning algorithm space O If the set-valued learning algorithm
(99
Consider discrete decision
A ................................ =RSW)
1
Σ
((0,z.) 2
min g
Σ
100 z2) +e
is used with 2 0, it holds that
max Pk
max Pa (0) 2 1 - Tk ( BEO
(35)
8
max 0E
Ph(0) Tn
(36)
and hence
E 2
8
ThhA 2 Tk
Tk
(37)
where Tk the tail probability defined Theorem
2.3
To prove Theorem C.11 also introduce some notations. For every non-empty subset W C use the following counterpart of Definition C.6 Let
θ
W = θ E
N W: L(0) s min L(0") + 8
(38)
N'ew
be the set of 8-optimal solutions in the restricted decision space W, and
W
0 E NE:::
K E (0, 24)
min N'EW k
110', 24) + 8
(39)
be the set of 8-optimal solutions of the SAA with an i.i.d. data set of size k.
Proof of Theorem C.I7 for ROVEs. Given the retrieved solution set S and the chosen c, the rest of Phase II of Algorithm exactly performs Algorithm on the restricted problem minges E [1(0, =)]
obtain 8n with the data z [n/2]+ Ion the set-valued learning algorithm 19 the chosen value and
k K2, B B2.
To show the upper bound for the unconditional convergence probability P (0,, & 6Px). note that
ssn #0) n { L((m) < min L(O) + c f60n E 0
BES
and hence by union bound we can write
P (0x & 026) <P(Sno'=0) =0) + [(θ.))
min I((0) + 6) BES
(40)
P PS 0) has bound from Lemma C.12 We focus the second probability.
For fixed retrieved subset S _ θ define the tail of the maximum deviation on S
k
T
Σ 1(0 2.) L(8) > >
sup k
It is straightffrward that (.)() < Tx(() where Ty is the tail of the maximum deviation over the whole
space O Since (c E [c. a) 1, we have
1 - S E
S
6-c
2
1
S
(
-TS
8 18-2
2
2
kg
2
2
29

---

Tk2 ((6 2/2) (c/2) < 1/5, we have Th ((6 - 2)62 + k2 (e/2) < 1/5 and subsequently
1 1-T5 (5 - (c/2) 4/5, and hence n 2 1 - ((6 ( T (c/2) 4/5 by
Lemma C.13 for Phase of ROVEs conditioned on S and c, therefore the bound (2 from Theorem
C.8 applies. Using the inequalities 35 and (36) to upper bound the min Pk Pk max np.8
Term in gives
IP L(f,)
> min L(0) + t BES
$ S
m
c 2/5 C1 max The (5)
2 The
(8-()
8 (8-r)
2 }>}}}
10g10g
+ +exp
B2
C3
min {c, -2} 2}
B2
= S
3 min
e 2/53 e-2/5,C
+ eep
2
min {c, 0
20
B2
< S 3 min
e 2/5 C2Tk2
exp
2
C3
Further relaxing [S] to B1 and taking full expectation on both sides give
P ((0.)) > min L(0) L(0)+ +0) < Bi 3 2/5 Tka
min fg, 5 -08 o)
B2
+ exp
BES
This leads to the desired bound (33 after the above bound is plugged into (40) and the bound 34 from Lemma C.12 is applied with K kj-
Proof of Theorem C.11 for ROVE. For every non-empty subset W C + and k2, we consider the indicator
ka
lz
J.W.
(21 W...
2kg) =
1(0,
zi) S min
1(0', 21) (2)++ Σ
tc) for & E W,c E (0,6/2),
N'EW
lo
which indicates whether solution 0 W e-optimal for the SAA formed by {z1,..., 2b2 }. Here we add and W to the superscript to emphasize its dependence on them. The counterparts of the solution probabilities Ps: Pk. Ps for O.W.c are
Pk.
W.r (0) == E
1 B.W. l2
(21 (2.....) 2kz)
Pk. (())()) E. 1. (zi...., 2k0
B.
Pkg
W.+ = B2
O.W.c
(sf..... 22g)
k2
b=1
We need to show the uniform convergence of these probabilities for 5/2 To do we define slighted modified version of 1 W,W.e
k2
k2
l2 Σ
O.W. (2 (Z1...., :=
2kn))
1(0,2))
< min
1(0', 2,) +e)
for 8 E W, E [0,6/2),
NeW 1o
im1
W.e- W.e- W.c be the corresponding coun- which indicates a strict e-optimal solution, and let Pka . . terparts of solution probabilities. For any integer m > we construct brackets of size at most 1 \/m to cover the family of indicator functions {1k2 0.W.e, E [0, 8/1] i.e., let let LPkk
W,5/2 (0)m) and
cu == 0,
E; = inf {& E [0, [0.8/2]: :k. (0) 2 i/m)
for Sis m',
Pk.
8
6m/41 == 2
30

---

where we assume that e;, i = O,... m' +1 are strictly increasing without loss of generality (otherwise we can delete duplicated values). Then for any c [Ec, 11+1), we have that
W.r W. (0)
W.r (0)
Weeti (0)
W.ri (0)
Pko
Pkz
Pka
Pka
Pka
Wee+1 (0) Pkzz
W.c+1
(0) + Pka
W.0+1 (0) Pkzz
Wie (0)
Weett (0) P
W.e++1 (0) +
Pkz
and that
W. (0) Pkka
(0)
Pkz 2 (0) Plzz
W.4+1 (f)
Pkz
W.r Fi (0) Pk2
W.r (0) + Pkg
W.o (0) Pkaa
W (0)
Pka
W.r (0) Pko
W.r (0)
Pku
Therefore
sup <E(0.8/2]
W.) Pkz
Pk2
(0)(
max max o5k5m
{ e ph (0)
Pkz
W.e (0)
pw.e (0) Pkz
Pkz
W.a
(0)
1
m
(41)
To show that the random variable in converges in probability, we note that the U-statistic has the minimum variance among all unbiased estimators, in particular the following simple sample average estimators based on the first [n/ka] 12 data
[n//ka]
Pka (0) = [n/k2
8. ( 1
k2
[n//aa
WW (0) = |n/k2 Pkz
(w)=-(0)
kk
1.
(0--(zzks (1)=(i11)+1:-- 1. Fkkg))
1=1
Therefore can write
27
E
max max { (W.ie(() (0) - Wies [w))
Ph2
-Pk2
Pka
W.a (0) - -Pke
Wiei- (0)0-((0)/))
+1
Σ
E
Wies (0) - Pii
ph))t((0))² (0))²
Wiei
+
(DW.er - Phz
Weet (0) 21)
0Sigm'+1
Σ
E
Wies (0)
Pkk
Wie (8)
E
(Pks
Wie
(0)
-k=
wiec( ")) +
0sism'+1
27 W.er (0) (0))
w.es (0) )r)
Σ
E
Pki
W.ar (8) - Pk5
+E
(W. (0) - Pka
0Sism'+1
since Pko
Wies (0)
and Pko
Wies (0) are conditionally unbiased for pkz W.ei (0) and pkz W..e. (0)
Σ 0Sism'+1
E E,
(DW (0) (0) Pka
W.e. (6)) (8))
'1]
27
+ E
(p (0)
Pka
W.cs (0) 27
21)
Σ
E
E.
(Pkg (pwier-1) (0) - -kka
WWee
(0)
27 "
+ E
(phe (0) - Pk
W.el (0)) )
usigm'+1
2
2
2 +
4
< 2m' + 2)
+
S (m + 2)
B2
(n/ko
B₂
n/ka
By Minkowski inequality, the supremum satisfies
sup CE [0,0)//
W. (8) - Pkz Pkz
W.e (.((8))
(0)
< V
(m - 2)
2
+
4
+
B₂
n
m
31

---

Choosing m such that m + 00, m/B2 - O and mkz/n + 0 leads to the convergence (.
w. (0) + 0 in probability. Since e has finite cardinality and has a fi- (0./2(0.8/2] Pk2 (0) P&
nite number of subsets, it also holds that
sup wgo.dew.ceo.8722
W.e Pho
(0)
Piua
W.r (0)
+ 0 in probability.
(42)
Recall the bound (54 from the proof of Lemma C.13 in Appendix D.7. Here have the similar bound ma
k2 (0) < IP W g Wo). and hence
Wi
(0) sup P WEs @ w =P (wor? & wo)
sup "E [0 BEWi
Pk
rE(0.8/2)
We bound the probability P (Wo)? g Wo more carefully, We let
D. min (L(6') L(0) 0 E e > L(()) 0,
Lxz (0) = 1 Av
(0,z)))
k2
and have
wol2 l/2
g no
(0) 5 (0) 8
U
2
0. st. L(0)>5
U
(x) L(0") L(0) L(0) < (x) L(0) 2
0 a. L(0)~1
U
(0) I((0') max {A, o) - ixg I((0)
2
8)
0.8 st. -(0))L(0)3)
by the definition of Ao
U
(0') I((") max
A
8 5
< 10, T(0)]
2
0
c
U
Ley(0') L(0") < - max
or Lis (0) - L( 2 max
A
5
2
4
2
4
0,8'
A
8 8 1
U
(0) L(Ø) 2 max
4 4 $
A
U
(0) (0) I(O)
2
4
A
sup
Li, (0) L(O)
>
where the last line holds because max (A./2 (A./2-8/4,6/4) 8/4,8/4) A./4. This gives
[.
sup max < BEWA Pkz
w.((O) Tke
+ 0 as k2 oc.
We also have the trivial bound (0.88/2 maxdew P
W.r (0) max Pka w.o 2 W/. where
the inequality comes from the fact that E
Eoew!
Pkz
W.O
(0)
1. Now choose k < such that
A
1
Tk2
for all ho 2 k.
4
2
2
32

---

and we have for all 12 2 k and all non-empty W C θ that
inf cc(0,6/2]
max BEW Pka
(0) max
Pkk
w.r(()
inf max Pka
2.((0)
(0)
sup max
Pka (0)
eEWi
cE [ NeW
cE|0.6/2| Bw ws
W
2 O
2 [
(43)
Due to the uniform convergence 42
we have
min inf W00.0/0
max (0)
Piz
Pka
(0)
min inf
Pkz
w.((0)
max
Pkz
OEWi
wce
E(0.5/2
NEW
oew.
in probability, and hence
min (e..//)
inf
max
Pk2 NEW
W.
max BEWi
Pbz
(2)( 50) - 0.
(44)
Finally, we combine all the pieces to get
(hn & }²0]
S ssn =0 u (0, & sos
Pku (0) =0}
s (sns* = =0 u
max Pku (0)
max BES
BES
s asns* = 0) u UEE>
inf (E(0)5/2)
max Pkz
(.((0)
max
Pkz
(0(())
50s
BES
S ssne 0}
u
min inf WCO (0.55/2
max Pk. NEW
(0)
Pku
s =0
DEWi
By Lemma C.12 have P (Snn 0) under the conditions that limsup Ex
and h1, n/ k1, B1 - co. Together with the condition P (e 2 5/2) - 0 and (44 conclude
On & 26 0 by the union bound.
D Proofs for Technical Lemmas
D.1 Proof of Lemma
By symmetry, we have that
U (31...... 2n)
Σ
((2 Zx(n))
bijection r:[m]-+[x]
where we denote [n]] == (1,.... n). Then, by the convexity of the exponential function and Jensen's 's inequality, we have that
E [eep((tU)]
E
exp t
Σ
bijection m=(n]>>[N)
< E n!
Σ
exp (t (((,())...,,
bijection m:/x][[n]
E lexp (t- 2(,,,).,,,,))).
This completes the proof.
33

---

D.2 Proof of Lemma
C.3
We first consider the direction U [x] 2 c. Let
s (Za(i- 11t1.......... 2k))
and
x( (( 2ks)
where the shorthand notation ft [ and wy are mutually independent and also indepen- dent from ; Zn , Then, since E [x] [<*]. for all t >> holds that
P PU - E [x]
c) = (exp (LU) 2 exp (4 (E [x] + e)))
exp (-( [x] c)) E exp (UU)
(4)
(45)
S exp (-t (E
<)) exp (tR*))
(26) cxp (-t [E [+] + c)) exp (tA)),
where we apply the Markov inequality in (i), step (ii) is due to Lemma C.2 and step (Mi) uses Jensen's inequality and the convexity of the exponential function. Due to independence,
R can be viewed as the sample average of á i.idd. Bernoulli random variables, i.e., ñ
Σi Bernoulli (E [s]). Hence, have that
t exp
eexp (tR) = E
Bernoulli (E [+|])
EP
exp
Bernoulli (E()))
(46)
1
(1 E [<=] +
E
[cc]
exp
where we use the moment-generrating function of Bernoulli random variables in the last line. Substi- tuting (46) into (45). have that
exp (-t (E +c)) [a (1- E [x]) [R]] exp ( [ f(t).
P ER
(47)
Now, we consider minimizing f(t) for > Let g() = log ft). then holds that
E [x|] exp (+)
g'(1) - [<] + <) +
(1 - E [x)) + E [M] exp
By setting g'(1) 0, it is easy verify that the minimum point of [(),, denoted by 1*, satisfies that
[d]
exp
E [n]
(1 E [x]) [E[+]+ +c)
(48)
[1
E
[x])
( [x] + c)
exp
[n]
(1
LE [x]
Substituting
gives
E [c]
E (1 [K] c) A(B[x]++)
PUU PU-EEN ER 2x)
IE [n]
(1 E [x]] (E [ + c)
E [A]
E[m] -C
E [
13/+]++7
E [x]]
[x] +
exp (- DKL. (E [K] [ [x])).
(49)
34

---

Since n/k & 2n, the first bound immediately follows from (49)
Since (kl(p)))) (1 pl| q), the bound for the reverse side U E [1s v -6 then follows
by applying the first bound to the flipped binary kernel 1 - x. and U. This completes the proof of Lemma
D.3 Proof of Lemma
To show 12)) some basic calculus shows that for any fixed the function g(p) = (1 p) In 1-P is convex in p. and we have that
1-9
((g) (q) --1.
Therefore ( 2 g(g) o' (p) 9) = q p. which implies 12 immediately.
The lower bound 13) follows from
(pl())
-pig - (1 pp) p) In(1 - q) + min fphnp+ p) p)}
peh:1->
Iv - y yng y 71n(1 - () - ln2 = - (n( - 7))))
This completes the proof of Lemma C.4
D.4
Proof of Lemma
By Definition
C.5
we observe the following equivalence
{PE
U
P
U (px(0) 2 Pk (0 c) DEO)P!
BEEYPA
Hence, by the union bound, it holds that
& S Σ (px 2 pa (O - c).
DEGIPE
We further bound the probability ((px(0) 2 Pu (fmaa) - c}} as follows
P (0) Pk (0max)
-c)
8 +
8 - E
I P (x( 2 Pa: (ftmax)
n
Ps (fmax) S P& (Bmuax)
(50)
2
2
8 +
S P (n(()) 2 (((0))p(00mt))))) (O
+PP
IP
pa (Omaax S Pk: (O
2
On one hand, the first probability in On the other hand, we have (0) < Ps (Omuxx) - ô for every @) by the definition of P Therefore we can slightly abuse the notation to write
50 is solely determined by and increasing in (x) = E jox (0)
E
P (px (0) 2 Pu (0 - e) s P (x((0) 2 pn (O
ph(()) = Pk ( 6)
2
8
+P pi (Omaax) S Spi (1
2
P (0) -px(0) 2 - e
<
(x( = pa (0
2
+P fúx (Q pa (mmax) <
E
2
Note that, with s(2ı,..., w) = 1 (0 A znz w) the probability (0) can be viewed as
U-statistic with the kernel n² (21, 24) = E [nt ...................... 2 w)) 2l.............................. =n). A similar representa-
35

---

tion holds for Py (fx as well. Therefore, we can apply Lemma C33
to conclude that
P Ph
PM
Σ
P (()x(0) 2 Pk (0k c)
PESIPA
TP pi (0) - pa)(0)= 2 8-6
$ |
ph pv(()) = Pk (0 8
2
-
+ IP
(0%
Pk (0
2
$ |9
exp
12
DKL.
Ph (0R
-
E
pk (0
2k
2
+ exp
n
DKL
PA (O
-
pk: (0
2k
2
which completes the proof of Lemma
C.9
D.5 Proof of Lemma C.10
We observe that P& (0) is an conditionally unbiased estimator for PA (0). i.e., E. [Fx = (0). We
can express the difference between P& (0) and Pk (0pax) as the sample average
Px Pk P (0
1
[1 E A -.. =b) 1(0 A(E))...,,;1)
B
whose expectation is equal to (0) (f We denote by
1 1(0 E A.......... xx4) for 0 E O
for convenience, where (=i:-.., 2 represents random subsample. Then by Bemstten's inequality, we have every t 2 0 that
P. (p=(()) (0 (0) Pa (Omaa)) 2 21) S Sexp -B. 2Var. (1 1 jmas)
4/3
(51)
Since
Var.(13 - gg < E. (13 1zmex) )² ppc(0) + (0 S 2pr (0 (0
and
Var. (1ă 18max)
5 Var. 13 1 1 gmaxx)
x E, (1 - 11 1 + I @mmax )
< - (0) + 1 - p (
S 2 - (01--x(0)) (x)),
we have Var.(1 1 1mmas)
I min (ox (Omax), prx (0)). Substituting this bound to 51 and taking t (0 Pk (0) lead to
P.
P& (0) - Pr (0maax 20)
(fx (O (0))
exp
- B
4min (0 ), 1 (0)) + 4/3 (pa(a px)
(ix (OFuxx) (1)(
exp
BB
4 4min (px
Pa (Bmax)) )} + 16/3 (px (Omiax) Pb (0))
B
(px (Omax)
irz (z))
< exp
6
min [px (0ma))))) ), 1 ixx(max }} + pu (fmma - ())
36

---

Therefore, we have that
P. On $ Pk)
=P.
U
(0)
max Pa (0)) 0'
Σ
P.
(x(
- -mxx PA (0') EE
Σ
P. (0x(0)
6E F
B
(px (f
:ox(0))2
Σ
exp
6
min (ix (Omax)
pa (0maxx
} + pr: (0max) pic(0)
6E
Note that the function x² s2/(min (pr (0 ), 1 Pa (0 }} + x) x [0, is monotonically increasing and that pa (Omaax pn (0) > for all 0 E O P Therefore, we can further bound the probability
B
2
P. On $ P%)
<
exp
(-6
[jnax min (1
ph
jmax
Noting that | < | completes the proof of Lemma C.10
D.6 Proof of Lemma C12
Let (......., =t) be a random subsample and P, be the probability with respect to the subsampling randomness conditioned on the data and the algorithmic randomness. Consider the two probabilities
P (AA(E...... 2x) E G²), P. (A(=i.... = E
We have 1 - Ek,6 = P (A(21....,
..... 2x) 0*), and the conditional probability
P ( = 0 (A(zi...., E E00)) (1 P.-P. (A(2 (A) E0)) B
Therefore we can write
PSSn = 0) = E 3[(1 (1- 11-P. (A(zi,.... .t) E = 81] + S p (P. (A() < 1- E
(1-
Ex, Bi
,52)
where the base of the natural logarithm. Applying Lemma C.3 with 1((2,..., Zxiww (A(a)...,;)0)) E 0*) gives
2 E 0*) < 1- E-En.
(- n
1 (1-Ea.)
Ex,6 1 En,o )
P P. P.
< exp
(-22 2k
DKL.
c
Further applying the bound 12 from Lemma to
C.4 to the KL divergence on the right-hand side leads
1- Ek.5
1
Ex,5
1
En.8
-11 (1-2) 2) (1 - Er,6),
DKL
1 Ex,8
In + 1 Ex,5
e
e
37

---

and
1 Ek,5
DKL
Ek,
Eki
DKL
Ex,0
e
Eke
1
(1 - &x,,6// - (1 Ek,6) +
1- E
In
by bound 12
e
e
Ex.
1
1-En, Enin
1 -
- -(1-3
1
N
In
In Ek, - + e.
e
W
In
1
In E - 1+
In EaE
Combining the two bounds for the KI. divergence we have
1 - Ek,8
P P. (A(zi.....
zx) 0²)
e
min
cxp
n
(1
2
(1 Ex,6)
( c² (
(1-1/e)
2k
Note that the second term on the right-hand side of exp( [1 Ex,) Thus, we derive that
52 satisfies that
(1-(11Ecs)/e) S
P P(sne 0) D)
n
(1- e) (1 - -EmS))
2)
(
(1-1/0) 2
B1(1 - Ek,))
< min
exp
+ exp
2k
1 - 2/e
(1 11--E EL.D))
E²Er,
(1 (1-1/e)
B1 En,55)
< min
exp
1 1/e
+
exp
The conclusion then follows by setting C4, Cs, Co: C7 to be the appropriate constants.
D.7 Proof of Lemma C.13
Let (0) = Ei_ 2.) Let 6* be an optimal solution of I We have
max pa (0) Z pk (0 P or @+ P (00 @1)
To bound the probability on the right hand side, we write
f002 g @t}
c
U
{is(0) > (0) +e}
0E89,0'EB
U
{in(0) - L(O) (x(0)) + L(0) L(0)
#E
U
{in(0) - L(O) > (N(0) - L(O') +c]
C
U
{in(0) - L())
or La(0') - L( < - 2
2
BEEP C'
C
U
(0) I(0)| 25
AEE
= max
(x) L(
2
DEB
38

---

therefore
max (b) 2 P BE0
max BEB
(0) - L(0) 2 2 - Ta
(53)
This proves
35
To bound the other term maxogo) Pk (0)) for any 0 E O 06 holds that
Pk (6) = P (o 6 S IP 0 2 8*
(54)
and hence maxggeres (0) S P O & 6*) To bound the latter, we have
0 & )
U
(L((0) Lx(0)+ +c]
0 1(0)
U
(L((0' L(O) L(0) L(0) S L.) L(0) L()) +c}
6.0 L(0))_
U
(x())) I(0) + (L) I(0) +c}
8 L(9') L
U
LA('') - L(O) < 8-c or L (0) L(0) > -
2
8,0'E0 L(8')
6-6)
U
(x) I(O)
2
BE9
(0) - L(0)
-
max AEO
2
therefore
8 -
max (a(0) < TP 6
max
(0)
L(O))
< Tk
(55)
8EB
2
2
This immediately gives (36)
37) is obvious given 35) and (36
E
Improving Tail Decay in Linear Regression
In this section, we present another example demonstrating that algorithm is capable of turning polynomial-tailed base learner into exponential. We consider the linear regression problem
min [[(0 (c(-1.1]
3)
(56)
where the data ((x,, v)) are i.i.d. samples such that x; E 1-1,1}- and y: = x,0" + C.-
Assumption E.1. The unknown true coefficient of problem (56) is 0" 0. The random variables {Ei)/ are i.i.d. distributed with zero mean and symmetric with respect to O. The second and forth moments of e, are finite, denoted as x² [<]] and μ* = E [<+]] Moreover, there exist constants C> O and a > 0 such that P(g > t) > C + +) for all f > 0, i.e., 6 has polynomial tail.
Under the setting described by (56) and Assumption E.1
the least-squares estimator of 0 is given by
0LS P(-1.1) i Tilli
n 2i=1 Σ x
TM Di=1
Tif;
-
P1-1.11
+ 0*
P(-1,1
n
where (1-1,1)(-) denotes the projection operator onto the interval [-1, 1]. Since the coefficient 0" = 0, for any estimator 0 that takes values between [-1, 1], its excess risk is equal to (0)2. For instance, the excess risk of gLS can be expressed
-"= 246
(0T-8)2 min
Theorem E.2. Under Assumption E.1 the followings hold true.
39

---

The excess risk of the sast-squares estimator 8 exhibits a potynomial tail in n. Specifically, for every 8 E (0, 1) and it holds that
P ((02))>>0)) -(nv
(57)
Under our ensemble method, the excess risk of the output estimator 0, has an exponentially decreasing tail.
E.1 Proof' of Theorem E.2
We first show the polynomial tail of excess risk for the least-squares estimator 0 For k n, let E = 1/k: Σ G be the sample average of the first noise terms. Then, it holds that cx+1 = (kC& + (x+1) (k + 1).
For every d E (0, 1) and 1, we have that
( ZiCi
P ((0L5)2 8) =P
=P
> 8
2P vo). (58)
n2
where used the symmetry of and that 2; {-1,1). Then, using the recursive relation between En and 1n we can further show that
P(G. > V8)= 2
1) (n
2 and
'n >
v8 v8)
n
n
P
(n 1)
P
En
v8)
(59)
n
n2
> P (Gn-1 2 0) C(nv
where the second line is due to the independence between En-1 and en in the second line, and the last line uses Assumption E.1 Since each is symmetric, have IP (ēn-1 2 0) 1/2. Hence, the proof of (57) is completed by combining (58) and (59).
Now, we proceed to show the exponential tail of excess risk for our ensemble method (Algorithm 2). where the proof is based on Theorem C.11 i.e., the formal version of Theorem [2.3 To apply the
bound 33 from Theorem C.I1 we need to derive upper bounds for the following two quantities:
empirical process tail (-), and the excess risk tail of the base learner, i.e., least-squares estimator 05.5 with & samples.
For any we can show that the empirical process tail satisfies that
(t) = 8E[-1,1]
sup
(x,0 - E[(x0 -) >t
P
sup
Σ (x,0 - -G)² - (02 + 02)
>
86|-1,1]
k 1=1
P
sup
2
02
22220 20
I:6
>
0E
1=1
t=1
1
2
<P
2
+
Σ
246
>
+P
0²
Σ
2 >
(60)
where the last inequality uses the union bound and the observation that the maximum of the absolute value term is achieved either at
1 or 0 -1. Using the symmetry of e, and the fact that
40

---

Ij E {-1,1}, we further derive from 60
that
k
2 /
(t) S 2P
0²
Σ
Gi
>
4
k i=1
1=1
k Σ
X 2P
o²
>
+ 21P
2
G
t
(61)
2
k
2
i=1
8/44
32
kt
kt
where we apply the union bound again in the second line and use the Markov's inequality in the last line.
Now, we assess the excess risk tail of the least-squares estimator 0.... For similar (58 can apply the Markov's 's inequality to show that
((2
g²
Ek (10 8) =P
6 I
(62)
k8
By instantiating 33 in Theorem C.11 with the tail bounds on (t)(t) and Ex,s given by 61 and we can finally obtain the following tail bound on the excess risk of our estimator 8,.:
62
32 + 402)
20222
P ((,,)² 8) s Bi 3 min
-2/5
2/5 C
+e BB/Os
l/ min {c, 8 - c)²
(63)
min { (1-11-1)) +tt/2///
Cs σ² W0gh
+ -B- B. (1-
2 /
kid
5 and hi 1. Note that these conditions guarantee that the upper bound in 63 is meaningful and that Tk ((8 c)/2) Thp (c/2) 1/5, required by Theorem 2.3 Therefore, conclude that the excess risk for the output solution 8, of our ensemble method has an exponential tail, which completes the proof of Theorem E.2
for every k1 22 and 5 E 10, such that 5 7,
400
32 32(
1=(0-
Kig
Additional Numerical Experiments
This section supplements Section We first provide details for the architecture the neural networks in Section [.I] and the considered stochastic programs in Section F22 Section [F3 |F33 presents a comprehensive profiling of hyperparamcters of our methods, and Section provides additional experimental results that evaluate our algorithms from various perspectives.
F.1
MLP Architecture
The input layer of our MLPs has the same number of neurons as the input dimension, and the output layer single neuron that gives the final prediction. All activations are ReLU. The architecture of hidden layers is as follows under different numbers of hidden layers H:
2: Each hidden layer has 50 neurons.
H 4: There are 50, 300, 300, 50 neurons from the first to the fourth hidden layer.
H There are 50, 300, 500, 500 300, 50 neurons from the first the sixth hidden layer.
H There are 50, 300, 500, 800, 800 500 300, neurons from the first to the eighth hidden layer.
41

---

F.2 Stochastic Programming Problems
Resource Allocation 866. The decision maker wants choose a subset m projects. A quantity of low-cost resource is available to be allocated, and any additional resource can be obtained at an incremental unit cost e. Each project has an expected reward rj. The amount of resource required by each project is random variable, denoted by W,. We can formulate the problem as
max 0E (0,1)
r2O CE
W.O:
(64)
In the experiment, we consider the three-proe prrre-product scenario, i.e., = 3, and assume that the random variable W, follows the Pareto distribution.
Supply Chain Network Design 66 Chapter 1.5]. Consider a network of suppliers, processing facilities, and customers, where the goal is to optimize the overall supply chain efficiency. The supply chain design problem can be formulated as a two-stage stochastic optimization problem
min (E(U,1)PP
Σ co E(Q(0, PEP
(65)
where P is the set of processing facilities, Cp is the cost of opening facility p. and is the vector of (random) parameters, i.c. (h, q, d, s, R, M) in (66). Function Q(0, 2) represents the total processing and transportation cost, and it is equal to the optimal objective value of the following second-stage problem:
miny20.200
q y + h
s.t.
Ny = 0,
Cy+ + 2 d,
(66)
Sy S.
Ry S M0,
where N, S appropriate matrices that describe the network flow constraints. More details about this example can be found in [61 Chapter 1.5]. In our experiment, we consider the scenario suppliers, 2 facilities, 3 consumers, and 5 products. We choose supply and demand d as random variables that follow the Pareto distribution.
Maximum Weight Matching and Stochastic Linear Program. We explore both the maximum weight matching problem and the linear program that arises from it. Let = (V, E) be a general graph, where each edge E is associated with (possibly) random weight we. For each node v E V, denote E(v) as the set of edges incident to v. Based on this setup, we consider the following linear program
max (i
E E WeOel E ag00 1 VOEV,
(67)
subject
where is some positive coefficient. When 0e = 1 for all e E E and is restricted to the discrete set {0. 1 66 is equivalent to the maximum weight matching problem. For the maximum weight matching, consider complete bipartite graph with 5 nodes on each side (the dimension is 25). The weights of nine edges are Pareto distributed and the remaining are prespecified constants. For the linear programming problem, consider 28-dimensional instance (the underlying graph an 8-node complete graph), where all w. follows the Pareto distribution.
Mean-Variance Variance Portfolio Optimization. Consider constructing portfolio based assets. Each asset i has a rate return r; that is random with mean (4: The goal is to minimize the variance of the portfolio while ensuring that the expected rate of return surpasses target level b. The problem can be formulated as
ming subject to
E
Di=l
m
(ri 1s)
Σ i=1 140 2
(68)
Σm
0:
0,
2 0,
Vi 1,...,
42

---

where 0 is the decision variable and each μi is assumed known. In the experiment, we consider scenario with 10 assets, i.., m 10. where each rate of return r; a linear combination of the rates of return of 100 underlying assets in the form ry /10(i-1)+1/2 + Σ}= r,/200. Each of these underlying assets has Pareto rate of return f..J 1,..., 100.
E.3 Hyperparameter Profiling
We test the effect of different hyperparameters in our ensemble methods, including subsample sizes k, A1, 22, ensemble sizes B, B1, B2. and threshold Throughout this profiling stage, we use the sample average approximation (SAA) as the base algorithm. To profile the effect of subsample sizes and ensemble sizes, consider the resource allocation problem.
We explored scenarios where & (equivalently k and k2) is both dependent on and independent of the total sample size (see Figures 6a 7a and/7) The results suggest that constant k generally suffices, although the optimal A varies by problem instance. For example, Figures 77 and show that l: 2 yields the best performance; increasing k degrades results. Conversely, in Figure 6a k = proves inadequate, with larger l delivering good results. The underlying reason is that the effective performance of MoVE requires 0* arg ga Ps (f). In the former, this is achieved with only two samples, enabling MoVE to identify 0* with a subsample size of 2. For the latter, a higher number of samples required to meet this condition, explaining the suboptimal performance at = 2. In Figure g we simulate ps (0) for the two cases, which further explains the influence of the subsample size.
Subsample Size.
Ensemble Size. In Figure 9 we illustrate the performance of MoVE and ROVE under different B, B1, B2, where we k ki h2 10 and 0.005. From the figure, we find that the performance of our ensemble methods is improving in the ensemble sizes.
Threshold e. The optimal choice of in ROVE and ROVEs is problem-depende and related to the number of (near) optimal solutions. This dependence is illustrated by the performance of ROVE shown in Figures and
and 6c Hence, we propose an adaptíve strategy defined follows: Let g(e) == 1/B2 Σ (0)
0 Kg (.)),, where we use ò, (e) to emphasize the dependency of 0,, on e. Then, we select ex == min {e: g(e)= 2 1/2]. By definition, g(e) is the proportion of times that (e) is included in the "near optimum set" 0%,b The choice of E" makes it more likely for the true optimal solution be included in the "near optimum set",, instead of being ruled out by suboptimal solutions. Practically, e" can be efficiently determined using binary search as an intermediate step between Phases I and To prevent data leakage we compute using Z (Phase data) for ROVEs. From Figure 6 we observe that this adaptive strategy exhibits decent performance for all scenarios. Similar behaviors can also be observed for ROVEs in Figure 10
Recommended Configurations. Based on the profiling results, we summarize the recommended configurations used in all other experiments presented in the paper (unless specified otherwise):
For discrete space θ, use k = max 10, n 22000), B = 200 for MoVE, and k1 k2 = max(10, (0,, n 2220)), B1 = 20, B3 200 for ROVE and ROVEs.
max (30, n /000) B1 50, B2 For continuous space θ, use k; max(33, n n/2), A- 200 for ROVE and ROVEs.
The in ROVE and ROVEs is selected such that max (1/B2) BB 1 E 6%-") R 1/2.
43

---

6-00
-10
18.7
cort
18.5
cook
-14
18.9
-16
12.2
sample 1i0
sample oze
somple 100
(a) Profiling for (MoVE).
(b) Profiling for (multiple optima).
Profiling (unique optima).
Figure 6: Profiling for subsample size k and threshold (a): Resource allocation problem, where
200; (b) and (c): Linear program, where 1 k2 = max(10, 0.005m). B1 = 20, and B3 = 200.
200 --- Soll 4-10
4-10
1w0.1
-3.15
-1.31
3.22
-222
sample
sample
sample
(a) Profiling for le (instance 1).
(b) Profiling for & (instance 2). (c) Profiling for (near optima).
Figure 7: Profiling results for subsample size k and threshold e. (a) and (b): Resource allocation problem using MoVE, where B 200: (c): Linear program with multiple near optima using ROVE,
where k = k2 max (0, 0.005n). B1 = 20, and B2 = 200.
F.4
Additional Experimental Results
Here, present additional figures that supplement the experiments and discussions in Section 3 Recall that MoVE refers to Algorithm| [ ROVE refers to Algorithm _ without data splitting, and ROVEs refers Algorithm
2 with data splitting. We briefly introduce each figure below and refer the reader to the figure caption for detailed discussions. Figures [ 19 follow the recommended configuration listed in Section
Figure
11
supplements the results in Figure with MLPs with H = 2, 4 hidden layers.
Figure
12
supplements the results in Figure with a different synthetic example than in Section 3.1
Figure 13 supplements the results in Figure with three other real datasets: Wine Quality 779
Online News (83), Appliances Energy [73]. ROVE and the base algorithm perform comparably on these three datasets, potentially because they are lighter tailed than those in Figure
Figure 14 shows results for MLP regression on a slightly different example than in Section
3.1
Figures 15 [6]sow results for regression with least squares regression and Ridge regression as the base learning algorithms respectively.
Figure 17
shows results on the stochastic linear program example with light-tailed uncertainties.
contains additional results on the supply chain network design example for different choices hyperparameters and a different problem instance with strong correlation between solutions.
Figure 18
In Figure 19 we apply our ensemble methods to resource allocation and maximum weight matching using DRO with Wasserstein metric as the base algorithm. This result, together with Figure where the base algorithm is SAA, demonstrates that the benefit of our ensemble methods is agnostic to the underlying base algorithm.
Figure 20 we simulate the generalization sensitivity ījk,8, defined in 27 which explains the superior performance of ROVE and ROVEs in the presence of multiple opumal solutions.
44

---

MoVE (AmOLLn)
MoVE (1-2)
base
01.4
Ploutput. suhopcimal solution)
1v((P)) IINNN0A PA/P)
0.2
10m-
01.
10h2
-0.1
27
sample sice
(a) Figure 6a
suboptimal probability.
(b) Figure 6a (0") maXe (l).
base
MoVE (1m0Lin)
MoVE (1-2)
0.15
Pooupput suboptimal
10
10
2
sample size
(c) Figure
suboptimal prohability.
(d) Figure 7a Px((") maxez0 (=)
Figure 8: Performance of MoVE (B = 200) in resource allocation, corresponding to the two instances in Figures 6al and 7a Subfigures (b) and (d) explain the behaviors of MoVE with different subsample sizes k: In (b), we find that pı (0*)
maxa Pk (0) < 0 for < 4, which results in the poor have p2(0") - max0 P2(0) 0.165,
performance of MoVE with k = 2 in Figure 6a In (d),
thereby enabling MoVE to distinguish the optimal solution only using subsamples of size two, which results in the good performance MoVE with ls
in Figure 7
(0-50
B-100
B-200
2-400
R.05
8, 100
2y0 -er R
-1.35
-1.23
-1.75
-1.22
-0.30
-1205
-1220
-1.35
-1.07
1,39
sample diz
sample dez
sample 5ize
(8) MoVE.
(b) ROVE with B, 200.
(c) ROVE with B, 20.
Figure 9: Profiling for ensemble sizes B, B₁, Bg in resource allocation. Subsample size is chosen
k kj = hg 10.
45

---

-15
-126
-137
102
CO02
-3.8
-100
2
24
sample
(a) Multiple optima.
(b) Multiple near optimum.
(c) Single optimum.
Figure 10: Performance of ROVEs in three instances of linear programs under different thresholds
The setting is identical to that of Figures 6b 6cc and 7c for ROVE. Hyperparameters: k1 l = max(10. 10, 0.005m), B1 20, and B, 200. Compared with profiling results for ROVE, we observe that the value of has similar impacts on the performance of ROVEs. Moreover, the proposed adaptive strategy also behaves well for ROVEs.
we demonstrate how the tail heaviness the problem affects the algorithm perfor- mance. The figure shows that the performance gap between ROVE, ROVEs, and the base algorithm becomes increasingly significant the tail of the uncertainty becomes heavier. This supports the effectiveness of ROVE and ROVEs in handling heavy-tailed uncertainty, where the base algorithm's s performance suffers. Note that here MoVE behaves similarly as the base learner due to optima multiplicity.
In Figure 21
ROVES
base
KOVE
KOVES
12a
10A
106
1.2
tal prob.
0014
COS2
20-1
10"2
cost
(a) Pareto noise, H = 2.
(b) Pareto noise, H1 6.
(c) Pareto noise, H = 2, 26
bare
ROVE
ROVEs
10
12a2
tall prob.
8
10"1
212
212 242
25
sample
sample
(d) Gaussian noise, Hl
Gaussian noise, H (l) Gaussian noise, H 2, 266
Figure 11: Results of neural networks with the same setup described in Section 3.1 (d)
Expected out-of-sample costs (MSE) with 95% confidence intervals under different noise distributions and varying numbers of hidden layers (H). (c) and (f): Tail probabilities of out-of-sample costs. In (a), ROVEs slightly underperforms the base learner probably due the weak expressiveness and hence high bias of the MLP with 2 hidden layers.
References
[66] Edward Anderson and Harrison Nguyen. When can we improve on sample average approxima- tion for stochastic optimization? Operations Research Letters, 48(5):566-577 2020.
[67] Irwan Bello, Hieu Pham, Quoc Le, Mohammad Norouzi, Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv:1611.0994/ 2016.
46

---

base ROVE
ROVES
GBOT
base ROVE
ROVES
GBDT
XGB
RF
XGB
100
tail prob.
tail prob.
10-1
10-1
10a
10a
cost
cost
(a) Pareto shape = 2.0, n 215
(b) Pareto shape 15,, n = 2
Figure 12: Results decision trees in terms tail probabilities of out-of-sample costs (MSE). The data generation is Y 10 > i= 2 sin(2 - 61 <2, where each X; is independently and uniformly drawn from [0, 1|. and é1, Eg are independent Pareto variables of the same parameters. Hyperparameters: Lj = mmx (30, n 10), k2 max(30,1/200), B1 = 50, Bg 200.
107
12a
105
tail groh
tall pr00
10
t211
10
10
10
7500
0200
B500
0000
9300
0.50
0.55
0.00
0.05
0.70
cost
Appliances Energy.
(b) Online News.
Wine Quality.
Figure 13: Results of neural networks with hidden layers another three real datasets, in terms of tail probabilities of out-of-sample costs (MSE).
base
ROVE
-
base
ROVE
ROVES
30
10a
4
3x30
tail prob.
cost
10-1
10-1
10-2
2.0
2
2.
sample size
cost
(a) Average performance with 95% Cls.
(b) Tail performance for n 216
Figure 14: Results with MLP of H 4 hidden layers. The setup is the same in Section
3.1 except that the dimension of X is now 30 and the data generation becomes Y (1/30) log( X, + 1) + where each X, is drawn independently from Unif 2 198(j - 1)/29).
47

---

base
+
ROVE
ROVES
ROVE
0.150
10
0.125
0.100
tail prob.
10
cost
0.050
0.025
10-2
0.000
250
24
22
23
2
2
2
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
sample size
(a) d 10.
(b) Tail performance. d 10,
2
base
+
ROVES
base
ROVE
ROVES
1.75
1.25
tail prob.
1.00
10
0.75
0.50
0.25
10
210
2
215
236
0.00
0.05
0.10
0.15
0.20
0.25 cost
0.30
0.35
0.40
sample size
(c)
(d) performance. 50, 2
Figure 15: Linear regression with least squares regression as the base learning algorithm. Given the input dimension d, the data generation is Y Σd (-10 + 20(i 1)/(d 1) + E2 where each X; is independent Uni + 18(i 1)/ 1)) and each Ej.J = 1, is Pareto(2.1) 12.1) and independent of X. (a) and (c): Expected out-of-sample error with 95% confidence interval. (b) and (d): Tail probabilities of out-of-sample errors.
[68] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' d'horizon. European Journal of Operational Research, 290-2):405-421, 2021.
[69] Timo Berthold and Gregor Hendel. Learning to scale mixed-integer programs, Proceedings of the AAAI Conference on Artificial Intelligence, 35(5):3661 011336661-668,,, 2021.
[70] Max Biggs, Rim Hariss, and Georgia Perakis. Constrained optimization of objective functions determined from random forests. Production and Operations Management, 32(2):397-415, 2023.
[71] Max Biggs and Georgia Perakis. Tightness of prescriptive tree-based mixed-integer optimization formulations. arXiv preprint arXiv:2302. /4744, 2023.
[72] John R Birge. Uses of sub-sample estimates to reduce errors in stochastic optimization models. arXiv preprint arXiv:2310.07052. 2023.
[73] Luis Candanedo. Appliances Energy Prediction. UCI Machine Learning Repository, 2017. DOI:
[74] Jessie XT Chen and Miles Lopes. Estimating the error of randomized newton methods: A bootstrap approach. In International Conference on Machine Learning, pages 1649-1659, PMLR, 2020.
[75] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer benchmark. Journal of Machine Learning Research, 23(189):1-59, 2022.
48

---

base
ROVE
ROVES
base
ROVE
ROVES
10
0.150
0.125
tail prob.
100
Cost
0.075
0.050
0.025
10"2
0.000
210
24
2
2
2
233
2
0.0
0.2
0.3
0.5
0.6
0.7
sample
cost
(a) d 10.
(b) Tail performance. = 10, 71 = 2
+ base
+ ROVE
ROVES
base
ROVE
ROVES
1.75
10a
1.25
tail prob.
1.00
10-1
0.50
0.25
10-2
0.00
210
2
2
25
2
0.00
0.05
0.10
0.15
0.20 cost
0.25
0.30
0.35
0.40
sample size
d 50.
(d) Tail performance. 50,
2
Figure 16: Linear regression with Ridge regression as the base learning algorithm. The same data generation as Figure 15 (a) and (c): Expected out-of-sample error with 95% confidence interval. (b) and (d): Tail probabilities of out-of-sample errors.
Iose
MoVE
ROVE
ROVES
Icee
MoVE
ROVE ..-.. ROVES
100:
7.5
-2.12
-2.150
-3.23
-..5
COCK
-3.95
-2.30
1100
2
sample sinz
sampp 5ioz
sample Siz
(a) Instance
(b) Instance 2.
(c) Instance
Figure 17: Results for linear programs with light-tailed objectives. The base algorithm is SAA.
49

---

base
MOVE
ROVE
- ROVES
MOVE
ROVE
ROVES
84.8
9.24000
9.23975
84.6
9.23950
9.23925
84.4
9.23900
9.23875
9.23850
9.23825
2'
2'
2 sample size
sample size
(a) 1: h1 K2 max n/10).
(b) A different instance with strong correlation.
Figure 18: Results for supply chain network design. (a): The same problem instance as in Section 3.2
under different hyperparameter choice: k = max (10, n 10), B 200 for MoVE and i = 2 max(10, n//1), B1 = 20, B2 200 for ROVE and ROVEs. (b): The same setup as in Section 3.2 on different problem instance for which the objectives under different solutions are strongly correlated. The strong correlation cancels out most of the heavy-tailed noise between solutions, making the base algorithm less susceptible to these noises, thus our ensemble methods appear less effective.
base
MoVE
+
ROVE
-:+- ROVES
base
MoVE
+
ROVE
..- ROVES
-3.00
-11.8
-11.0
COSt
-3.10
cost
-3.15
-11.42
-3.20
2
2
2
2
2.0
2
sample size
sample size
(a) Resource allocation.
(b) Maximum weight matching.
Figure 19: Results for resource allocation and maximum weight matching when the base algorithm is DRO using I-Wasserstein metric with the Lx norm.
[76] Xiaohan Chen, Jialin Liu, and Wotao Yin. Learning to optimize: A tutorial for continuous and mixed-integer optimization. Science China Mathematics, pages 1-72, 2024.
[77] Xiaotie Chen and David I. Woodruff. Software for data-based stochastic programming using bootstrap estimation. INFORMS Journal on Computing, 35(6):1218-1224 2023.
[78] Xiaotie Chen and David I. Woodruff. Distributions and bootstrap for data-based stochastic programming. Computational Management Science, 21(1):33, 2024.
[79] Paulo Cortez, A. Cerdeira, F. Almeida, T. Matos, and J. Reis. Wine Quality. UCI Machine Learning Repository, 2009. DOI:
[80] Arnaud Deza and Elias B Khalil. Machine learning for cutting planes in integer programming: a survey. Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 6592-6600, 2023.
[81] Andreas Eichhorn and Werner Römisch. Stochastic integer programming: Limit theorems and confidence intervals. Mathematics of Operations Research, 32(1): 2007.
[82] Yixin Fang, Jinfeng Xu, and Lei Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19(78):1-21, 2018. 2018.
50

---

MoVE (f-10) 10)
MoVE 50)
ROVE (A=10)
ROVE (k-50)
0.15
0.10
0.06
0.00
0.0
0.5
1.0
1.5
2.0
3.0
3.5
6
Figure 20: Comparison of 7).55 for MoVE and ROVE in linear program with multiple optima
(corresponds to the instance Figure
5d). Threshold chosen as 4 when kj = 4- 10
and 2.5 when &: k hi
50, according the adaptive strategy. Note that fjk,6 =
maxsge Pk (0) maxpger Pk by 27 which measures the generalization sensitivity. For
MoVE, have (0) P(OSAA 0); and for ROVE, have pı:(0) P(O @ where θj is the <-optimal set of SAA defined in (23). From the figure, we can observe that the issue brought by
the presence of multiple optimal solutions be alleviated using the two-phase strategy in ROVE.
base
MoVE - ROVE .... ROVEs
0.6
Ploutput suboptimal solution)
0.5
0.3
0.1
3.0
3.5
4.0
4.5
5,0
5.5
tail heaviness parameter
Figure 21: Influence of tail heaviness in the stochastic linear program with multiple optima with 105, Hyperparameters: k = 50, B 2000 for MoVE, ki k2 50, B1 200, B3 5000
for ROVE and ROVEs. The tail heaviness parameter corresponds to the mean of the Pareto random coefficient.
[83] Kelwin Fernandes, Pedro Vinagre, Paulo Cortez, and Pedro Sernadela. Online News Popularity.
UCI Machine Learning Repository, 2015. DOI:
[84] He He, Hal Daume III, and Jason M Eisner. Learning search in branch and bound algorithms. Advances in neural information processing systems, 27, 2014.
[85] Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), 2016.
[86] Anton Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approximation method for stochastic discrete optimization. SIAM Journal on optimization. 42(2):49-502, 2002.
[87] Henry Lam and Huajie Qian. Assessing solution quality in stochastic optimization via bootstrap aggregating. In Proceedings of the 2018 Winter Simulation Conference, pages 2061-2077 IEEE, 2018.
51

---

[88] Henry Lam and Huajie Qian. Bounding optimality gap in stochastic optimization via bagging: Statistical efficiency and stability. arXiv preprint arXiv:1810.02905, 2018.
[89] Miles Lopes, Shusen Wang, and Michael Mahoney. Error estimation for randomized least- squares algorithms via the bootstrap. In International Conference Machine Learning, pages 3217-3226. PMLR, 2018.
[90] Georgia Perakis and Leann Thayaparan. Umotem: Upper bounding method for optimizing over tree ensemble models. Available SSRN 3972341, 2021.
[91] Lara Scavuzzo, Feng Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with tree mdps. Advances in Neural Information Processing Systems, 35:18514-188
2022.
[92] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszezynski. Lectures on stochastic programming: modeling and theory. SIAM, 2021.
[93] Yunzhuang Shen, Yuan Sun, Andrew Eberhard, and Xiaodong Li. Learning primal heuristics for mixed integer programs. In 2021 international joint conference on neural networks (ijenn), pages 1-8. IEEE, 2021.
[94] Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning to cut. In International conference on machine learning, pages 9367-9376. PMLR, 2020.
[95] Keliang Wang, Leonardo Lozano, Carlos Cardonha, and David Bergman. Optimizing over an ensemble of neural networks. arXiv preprint arXiv:2112.07007, 2021.
[96] Jiayi Zhang, Chang Liu, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan, Yawen Li, and Junchi Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing. 5 519:205-217, 2023.
[97] Yanjie Zhong. Todd Kuffner, and Soumendra Lahiri. Online bootstrap inference with nonconvex stochastic gradient descent estimator. arXiv preprint wrxiv:2306.02200 2023.
52


Reviews:
[{"review_id": "iJPqLgH1z3", "reviewer": "Reviewer_jhTV", "summary": "This paper investigates a new ensemble learning approach that leverages subsampling to dramatically improve the tail behavior of generalization error. In contrast to classical bagging (which reduces variance by averaging outputs of multiple models), the authors propose to aggregate at the parameter/model level rather than just the output level . Specifically, they train many models on random subsamples of the data and then select a final model via a majority-vote scheme across those subsamples. The main theoretical result is that this procedure yields an exponentially decaying tail for the excess risk (generalization error)\n– even when each individual “base” learner only achieves a polynomial (slow) tail decay . In other words, with high probability the ensemble’s error is as small as the best model’s, providing a form of oraclelevel performance guarantee. This improvement is agnostic to the base learning algorithm: it holds for standard empirical risk minimization as well as more robust schemes (e.g. distributionally robust optimization or regularized methods) . The paper introduces a family of methods (named MoVE, ROVE, and ROVEs) to implement this idea, and demonstrates in experiments that these ensemble methods significantly improve out-of-sample performance on tasks with heavy-tailed data or inherently slow convergence rates. The authors also provide open-source code for their ensemble algorithms, supporting reproducibility.", "questions": "1. Clarification of the \"Majority Vote\" Process: Could you likely explain how the model selection process works in more specific terms, maybe by using a simple algorithmic pseudo-code? This statement was a little perplexing. For example, if the model parameter space is continuous, how does a \"vote\" work? It would help readers and practitioners use the procedure correctly if it were made clear whether this means picking the model that does best on most subsample runs and how ties or near-ties are handled. What criteria on the model class cause several subsamples to converge to the same \"majority\" model?\n\n2. Assumptions for guarantees of exponential tails: The idea says that the tails of excess risk will decrease exponentially. What assumptions about the data or the base learner must be true for this assurance to hold? For example, do we need a finite second moment or only a moment condition on the loss distribution? If the data has a very heavy tail (for example, infinite variance), does the ensemble still get an exponential tail, or would the rate improvement be limited? It would be beneficial for the paper to clearly describe the criteria (e.g., “the loss belongs to class $\\mathcal{H}_\\alpha$” or analogous statements) under which Theorem 1 (or the principal conclusion) is valid. This tells readers when it's okay to use the method.\n\n3. Cost and scalability of computing: The ensemble trains $B$ models on subsamples. What advice can you give on how to choose $B$ (the size of the ensemble) and the subsample percentage in real life? The trials probably employ some defaults, but it would be helpful if the paper talked about the trade-offs (more models for greater tail assurance vs. higher computation). Also, have you tried the method on bigger problems, such deep neural networks or big datasets? If not, do you think there will be any problems (like problems with optimization or too much variation in the outcomes of subsamples) when you scale up? It would be helpful to include some examples or explanations of how performance becomes better as $B$ gets bigger.\n\n4. Comparison to Other Robust Methods: How does the subsampled ensemble stack up against other robust methods for heavy tails, including applying a robust loss function (like Tukey's loss or trimmed mean aggregation) or the median-of-means applied directly to outcomes? Kwon et al. (2021) specifically suggested a robust model selection utilizing MOM—how does your methodology vary or exhibit greater generality? A clear explanation of how this method is different from median-of-means or bootstrap-of-means methods would make the newness clearer. For example, can a basic median-of-means estimator on the losses fail to produce exponential tails while your model-selection method works? Such information would help readers know when to choose the suggested ensemble over other strong estimators.\n\n5. Things to think about in the real world and examples of how to use it: The paper centers on heavy-tailed synthetic or regulated trials. Can you give me any instances of real-world datasets or areas where you think base learners will only have polynomial tail decay and will benefit a lot from your method? For example, would this be useful for reinforcement learning (where returns can be heavy-tailed), financial risk models, or any other big benchmarks? It would also be helpful to talk about the ensemble's failure modes, such as when subsampled voting might impair performance or not produce an exponential tail (for example, if the subsamples are too small to train usable models or if the data aren't heavy-tailed at all). This kind of advice would help practitioners who are thinking about using this ensemble technique make their work more useful.", "limitations": "The main problem with this task is that it takes a lot of computer power. To get the exponential tail bound, you need to train and test a lot of models on different data sets, which might be costly. This could make training take a lot longer in situations like deep learning than it would with just one model. Another problem is that the theory only looks at the worst-case tails of the error distribution. When the ensemble tries to get the best performance in the worst-case scenario (high-confidence bounds), it might give up some average-case accuracy or introduce bias. For example, it might choose a model that is safer but not quite as good on average. Users should know that the strategy works best when there are genuine concerns of heavy tails; otherwise, a smaller ensemble or single model can be enough. There is also a statistical limitation: the method implies that we can accurately find the \"best\" model by looking at how well it does on a subsample. If the number of subsamples $B$ is too small or if the performance of the subsamples is sufficiently noisy, most of vote could choose a model that isn't good enough. In rare circumstances, as when the subsamples are very small or the model classes are very complicated, the ensemble could not work better and could potentially make things worse because the voting results are unstable. These subtleties imply that the method necessitates meticulous adjustment of $B$ and subsample size, and perhaps requires validation using a hold-out set, if feasible.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strength : The paper presents a new ensemble learning framework that significantly enhances theoretical approaches for learning with heavy-tailed data distributions, a complex scenario frequently encountered in safety-critical fields like finance, medicine, and systems influenced by noisy or adversarial inputs. The authors show that the suggested ensemble method can turn polynomially decaying generalization tails into exponentially decaying ones. This is a big step forward in learning guarantees, not just a small one. This is especially important for situations when high-confidence reliability is very important. The method is also base-learner agnostic, which means it might be a powerful and versatile \"wrapper\" that makes a number of existing learning algorithms more resilient. The work is well-organized and written in a formal academic language, with well defined terms (such \"excess risk\" and \"tail decay rate\") and descriptive names for the approaches (MoVE, ROVE, ROVEs) that make it apparent what they do. Each approach is also put in context by explaining what it's for, and the theoretical ideas are backed up with clear explanations and strong visuals, such figures and examples, that help make sense of how the methods work when there are heavy-tailed situations.\n\nWeaknesses : The paper has some good points, but it also has some problems when it comes to being easy to read, useful in real life, and useful in a wider sense. The main idea behind this method is to choose a model by majority vote, however the way it is presented could be misleading. Many readers could think of \"majority voting\" in the traditional sense (i.e., voting on predictions) instead of voting on the models themselves. This unusual framing, which doesn't include an early, step-by-step pseudocode or algorithm description, makes it harder to understand. Also, important details like how to choose the number of subsampled models ($B$) or the best subsample sizes are not stressed in the main text and may be hidden in the appendix. This makes it tougher for readers to use or duplicate the strategy in real life. The method's practical applicability may be confined to specific contexts, with its benefits being most evident in situations characterized by heavy-tailed loss distributions or suboptimal convergence behavior. In typical ML applications characterized by sub-Gaussian noise or well-behaved distributions, the ensemble may provide minimal to no advantages compared to simpler bagging or robust loss techniques. Also, the predicted exponential improvements can be asymptotic, which means that we don't know if we can see real advantages at realistic sample sizes (like $n = 10^4$). In general, the method looks good on paper, but it might not be used in real-world ML pipelines until it is tested further, made simpler, and given clearer instructions for how to use it.", "was_revised": true, "final_justification": "I have look at the rebuttal and somewhat satisfied with the discussion and hence improve the score.", "rebuttal": "Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.\n\n> **Q1:** Confusing usage of the term \"majority vote\"\n\n**A1:** We will update the relevant part of the introduction as follows. To avoid the confusion between our procedure and the widely known majority vote in ensemble classification, we will no longer quote the phrase \"majority vote\" at the outset, but first describe the procedure in plain English, e.g., \"selecting the model that is most frequently output by the base learner\", and then identify it as a counterpart of the widely known majority vote for selecting models (as opposed to classes). This applies to discrete $\\Theta$. If the review still thinks it's misleading, we are happy to replace the phrase \"majority vote\" with more distinguishable terms such as \"mode finding\" throughout. For general (including continuous) $\\Theta$, the vote is preceded by a step that retrieves a finite set of high-quality models to vote on, thereby addressing the \"each model appearing at most once\" issue in directly copying the procedure from discrete to general $\\Theta$.\n\nA short description of the procedure is to select the model that does best on most subsample runs as the review suggests, but the notion of \"best\" here is determined by what the base learner attempts to optimize. Tie-breaking can be done arbitrarily as mentioned in line 99, and convergence theory is provided in Theorem 2.1.\n\n\n> **Q2:** Assumptions for guarantees of exponential tails\n\n**A2:** For our key result Theorem 2.1, the only required technical condition is $\\eta_{k, \\delta}:=p_k^{\\max }-\\mathcal E_{k, \\delta} > 0$ as stated in line 116. An informal interpretation of this condition is that the base learner generates $\\delta$-optimal solutions more often than other solutions (but not necessarily exponentially more often). We choose not to use more specific conditions such as moment conditions on the loss and structural conditions on the model class that imply our condition, in order to 1) make the theorem more general and 2) show a direct contrast between the tail of the base learner and that of our ensemble method. Indeed, our condition will hold for large enough $k$ and $\\delta$ as long as the base learner is weakly consistent, i.e., converging to optimal solutions in probability as $k\\to\\infty$. Weak consistency is a rather weak requirement that does not need finite high-order moments. On the other hand, our explicit bound (10) clearly demonstrates how the tail $\\mathcal{E}_{k,\\delta}$ of the base learner is improved by the ensemble.\n\n\n> **Q3:** Cost and scalability of computing\n\n**A3:** Like other machine learning algorithms, in practice the hyperparameters $k$ and $B$ can be tuned via techniques such as cross validation. On a technical level, the subsample size $k$ controls a tradeoff between the bias and the tail of method: Using a large $k$ in our method does not inflate the bias against the groundtruth but also may not be able to shrink the tail due to the small ratio $n/k$, whereas a small $k$ helps shrink the tail but may enlarge the bias. As for $B$, increasing $B$ typically improves the performance, but our bound also shows a value larger than $\\mathcal{O}(n/k)$ does not provide further benefit. We will update relevant discussion in lines 133-138. We also kindly refer the reviewer to Appendix F.3 for our configuration recommendation that works well for most problems we consider in the experiment. Regarding the computation cost in repeated training, we argue that this is common for all ensemble methods, and this is less significant for our method because subsample training are parallelizable. See Figure 7 for an experiments on the effect of $B$ on the performance.\n\n> **Q4:** Comparison to other robust methods\n\n**A4:** We have provided a comprehensive comparison between our method and robust techniques such as MOM and truncation-based methods in lines 289-303. As discussed there, MOM approaches require squared loss and/or convex function classes whereas our method only relies on the weak convergence of the base learner and thus is free of these conditions. Thanks for pointing out the work Kwon et al. (2021), and in their paper focuses on the squared loss and requires 4-th moment conditions. We will add this reference in the paper.\n\n\n> **Q5:** Things to think about in the real world and examples of how to use it\n\n**A5:** The reviewer is correct that our method is most useful for heavy-tailed problems, such as those from finance and physics. We try our method on several real-world datasets from the UCI repo, and found ROVE useful in predicting energy yield for gas turbines and critical temperature of superconductors:\n\n- Gas turbine data\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|1.907|2.477|2.762|3.022|3.633|4.368|\n|ROVE|1.746|1.853|1.905|1.968|2.024|2.05|\n\n- Superconductivty data\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|202.04|221.318|249.03|276.546|286.248|296.915|\n|ROVE|204.562|210.36|213.277|215.045|216.227|217.942|\n\nHere we list the percentiles of the test error of the base learner and our ROVE algorithm to compare their tail performance. We run each method multiple times on the data set, and each time we randomly split the data into training and testing and evaluate the trained models on the testing set.\n\nIn cases where the problem is not heavy-tailed our method usually perform comparably with the base learner or only brings marginal improvement as demonstrated by our experiments."}, {"review_id": "n1nsaR4hIl", "reviewer": "Reviewer_s98Y", "summary": "This paper introduces a novel ensemble learning method comprising MoVE (Majority Vote Ensembling) and ROVE (Retrieval and $\\epsilon$-Optimality Vote Ensembling), which leverages subsampling and model selection strategies to achieve exponential decay in excess risk, claiming to significantly outperforming traditional ensembling techniques which have polynomial decay, particularly in heavy-tailed data distributions. By training multiple base learners on data subsets and combining them through majority voting or likelihood-based retrieval, the approach ensures stronger generalization even when individual learners exhibit only polynomial decay in excess risk. Theoretical analysis confirms the presence of exponential tails in the generalization error. Experiments were conducted on: the MLP regression problem with synthetic data; four discrete stochastic programs: resource allocation, supply chain network design, maximum weight matching, and stochastic linear programming; and one continuous: mean-variance portfolio optimization, showing improved results.", "questions": "1. As claimed by the authors, classification is not addressed here due to the cross-entropy classification loss. It is somewhat reasonable but am not entirely convinced. Heavy tailed distribution can show up when the number of classes becomes very large, e.g. thousands, and we change our view point to the distribution of the classes. In such case it would be very interesting to see how the proposed approaches here perform. Do you have any comment on this point?\n\n2. I have a suggestion in mixing the approaches here with gradient boosting, which may be worth exploring. You can use MoVE/RoVE/RoVEs as a base learner at each iteration of gradient boosting, limiting to a small, managable size $B$ at each iteration. In such a way, you have a strong base learner than decision stumps that gradient boosting approaches are using. It would be interesting to see if such a mixed approach could lead to a result that is better than both vanilla gradient boosting and MoVE/RoVE/RoVEs.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "One-line summary: the paper is strong in theoretical contributions but, at least to me, not totally convinced in terms of practicality. My initial rating is based on my assessment that the theoretical contributions slightly outweigh the practical concerns.\n\n## Strengths\n\n1. This is a paper that is very solid in terms of theoretical contributions but well-written in such a way that the audience can manage to follow. Example 1.1 is particular useful in terms of motivating what the paper mainly contributes: even if base learners have polynomial decay in excess risk, classical bagging approach would result in polynomial decay but with the paper's proposed approaches, one can obtain exponential decay.\n\n2. Apart from the main theoretical contribution, which is exponential decay instead of polynomial decay, there are a number of small theoretical contributions in deriving the main contribution: a sharper concentration result for U-statistics with binary kernels improving upon Bernstein-type inequalities, analysing regret sensitivity, and developing a uniform law of large numbers (LLN) for $\\epsilon$-optimal events. \n\n3. Experimental results support the theoretical claims.\n\n## Weaknesses\n\n1. Although the main claim is about going from polynomial decay to exponential decay for the excess risk, I do not think this is too big of a claim because it is well known that in classification we have exponential decay. I maybe wrong but perhaps in regression the best bounds have not approached exponential decay yet and this paper fills in that missing link.\n\n2. In practice, when it comes to ensemble learning these days it is very popular to use gradient boosting (e.g. XGBoost or LightGBM for implementations) for both regression and classification problems as it has shown successes in many benchmarks. Cited in the paper but gradient boosting is nowhere to be found in the experiments, which is a big surprise to me. I think gradient boosting should have served as a strong baseline to compare against, alongside any bagging approach. Why? Because problem-wise, these approaches solve the same problem. In contrast, bagging and even advanced bagging approaches like random forests, are no longer very popular, as they are not as performant as gradient boosting. Gradient boosting approaches have a difference, maybe strength (which I may be wrong), over the proposed MoVE/RoVE/RoVEs approaches here in that they build new base learners based on the performances of previous base learners, whereas the approaches here build all base learners at once initially. Although the theory side may be lacking, intuitively such strategy that gradient boosting adopts may lead to a faster exponential decay rate.\n\n3. Although the idea of majority voting sounds interesting at first, it seems to come with more drawbacks than benefits. In order to do majority voting, you have to discretize the parameter space $\\Theta$. In this deep learning era where model weights are in the order of billions, discretizing the parameter space does not sound practical. Initially MoVE only works with discrete $\\Theta$. The authors have come up with the $\\epsilon$-optimal notion and derived RoVE/RoVEs to work with continuous $\\Theta$, which appears to be an attempt to \"cluster\" the continuous $\\Theta$ into a countable set of models that the algorithms can manage. However, when accuracy becomes highly demanded, one has to bring down $\\epsilon$ very close to 0. But that might explode exponentially the number of discrete models that the algorithms have to train. Wouldn't that mean $B$, the ensemble size, also has to be increased exponentially? The proposed theory treats $B$ as a constant (relying on $n/k$ only to be more precise), which, I think, has a tendency to hide the complete view.  $B$ deserves to have deeper analysis, especially when $\\epsilon$ becomes very close to 0.", "was_revised": true, "final_justification": "The rebuttal has made the paper more clear. I have read other reviews and rebuttal. I have revised my score accordingly.", "rebuttal": "Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.\n\n> **W1:** Significance in going from polynomial to exponential decay\n\n**A:** It is correct that in classification the widely used cross-entropy loss is inherently light-tailed, but in regression the loss function can be heavy-tailed and our method improves the tail decay from polynomial to exponential. There are existing methods such as MOM and truncation-based methods as discussed in Section 4 that can provide such tail enhancement under certain structural conditions on the model class or for certain types of loss functions, but our method is the first that is free of these restrictions.\n\n> **Q1:** Classification with many classes\n\n**A:** In classification with infinite number of classes, the distribution of the loss is exactly the distribution of the (minus) log probabilities of the classes. Therefore in theory the loss can be heavy-tailed if the log probabilities are heavy-tailed, but in practice, it may not be that likely for a log value to be heavy-tailed.\n\n\n\n> **W2:** Comparison to modern ensemble methods\n\n**A:** We have added a new set of experiments comparing our approach with popular existing tree ensembles, including Random Forest (RF), Gradient Boosted Decision Trees (GBDT), and XGBoost (XGB). Decision trees are used as the base learner for all methods. Random forests are constructed with the same number of decision trees as our methods to ensure a fair comparison. GBDT and XGB are constructed with early stopping to avoid overfitting. Results on percentiles of the test errors are as follows:\n\n\n## Comparison with tree ensembles in terms of tail performance\n### For the same synthetic data as described in lines 209-212\n- $n=2^{11}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|19.664|38.005|81.457|193.69|492.9|2035.014|\n|ROVE|3.455|4.431|4.943|5.569|6.153|6.323|\n|ROVEs|2.309|3.056|3.4|3.978|4.261|4.547|\n|RF|1.016|2.683|4.617|6.5|32.222|210.42|\n|GBDT|0.787|1.825|3.415|6.81|30.019|87.736|\n|XGB|1.635|5.092|9.101|21.094|52.973|105.72|\n\n\n- $n=2^{11}$, Pareto shape = $2.0$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|2.55|3.436|4.734|6.184|9.825|24.89|\n|ROVE|0.927|1.116|1.238|1.329|1.489|1.604|\n|ROVEs|0.665|0.832|0.907|0.987|1.035|1.094|\n|RF|0.121|0.181|0.249|0.326|0.757|2.789|\n|GBDT|0.114|0.184|0.246|0.324|0.819|1.057|\n|XGB|0.289|0.573|1.082|2.279|3.711|6.764|\n\n\n- $n=2^{11}$, Pareto shape = $2.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|0.845|0.994|1.138|1.315|1.599|2.415|\n|ROVE|0.389|0.448|0.502|0.535|0.62|0.65|\n|ROVEs|0.289|0.353|0.382|0.41|0.431|0.44|\n|RF|0.044|0.053|0.062|0.073|0.102|0.189|\n|GBDT|0.043|0.06|0.074|0.087|0.105|0.116|\n|XGB|0.103|0.173|0.248|0.421|0.588|0.913|\n\n\n### For a new synthetic data $Y=10\\sum_{i=0}^{9}2^{-i}\\sin(2\\pi X_i)+\\epsilon_1-\\epsilon_2$ where each $X_i$ is uniform on $[0,2]$ and $\\epsilon_1,\\epsilon_2$ are Pareto\n\n- $n=2^{15}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|46.095|103.303|193.074|364.772|640.562|1287.311|\n|ROVE|17.683|18.981|19.483|20.908|21.484|22.072|\n|ROVEs|17.907|19.262|20.444|21.171|21.715|23.893|\n|RF|6.518|10.507|18.519|34.58|46.284|79.079|\n|GBDT|21.61|40.734|59.422|87.771|136.325|232.915|\n|XGB|31.989|46.385|72.751|207.12|496.714|596.137|\n\n\n\n- $n=2^{15}$, Pareto shape = $2.0$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|6.341|7.251|7.924|9.374|12.617|18.885|\n|ROVE|8.975|9.248|9.413|9.501|9.563|9.683|\n|ROVEs|10.95|11.299|11.506|11.602|11.706|11.821|\n|RF|4.18|4.274|4.322|4.477|4.583|4.742|\n|GBDT|2.699|4.052|6.68|9.019|12.409|18.297|\n|XGB|5.77|8.136|10.154|13.496|17.501|28.473|\n\n### For a new synthetic data $Y=10\\sin(2\\pi X)+\\epsilon_1-\\epsilon_2$ where each $X$ is uniform on $[0,2]$ and $\\epsilon_1,\\epsilon_2$ are Pareto\n\n- $n=2^{15}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|35.753|84.013|149.819|267.985|423.76|665.424|\n|ROVE|5.969|7.133|7.808|8.481|9.272|9.704|\n|ROVEs|4.633|5.347|5.902|7.043|7.916|10.408|\n|RF|2.967|7.792|14.225|22.411|36.374|62.494|\n|GBDT|6.247|15.913|31.117|50.551|72.74|178.967|\n|XGB|3.636|6.206|8.579|13.917|25.043|27.09|\n\n- $n=2^{15}$, Pareto shape = $2.0$\n\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|1.944|2.579|3.479|4.35|5.367|7.477|\n|ROVE|0.889|0.997|1.065|1.11|1.149|1.264|\n|ROVEs|0.726|0.824|0.874|0.936|1.023|1.049|\n|RF|0.165|0.245|0.307|0.377|0.529|0.637|\n|GBDT|0.732|0.924|1.129|1.431|1.659|2.511|\n|XGB|0.331|0.443|0.568|0.687|0.875|1.007|\n\nThese results show that our methods outperform the base learner in almost all cases, and also outperforms RF, GBDT, and XGB especially in high percentiles when the tail is heavy (e.g., with Pareto shape 1.5). For not so heavy-tailed cases RF, GBDT, XGB may outperform our methods.\n\n\n> **Q2:** Mixing our method with gradient boosting\n\n**A:** Thank you for your insightful comments. We greatly appreciate your suggestion regarding integrating our approach with gradient boosting. We agree that using the base learner selected by MoVE/RoVE/RoVEs to replace the plain base learner can possibly strengthen the overall model compared to the two individual approaches. We will carefully consider this mixed strategy in our future study.\n\n\n> **W3:** Exponentially growing ensemble size?\n\n\n**A:** We have rigorouly investigated how the accuracy of the retrieved model set (measured by the excess risk of the best model in the set) scales with the ensemble size $B_1$. Our result (Lemma C.12) in line 1021 shows that in order to retrieve an $\\delta$-optimal model with high probability, the ensemble size can be set to the order $O(\\frac{1}{1-\\mathcal E_{k,\\delta}})$. This is straightforward to understand: Each model trained on a random subsample is $\\delta$ optimal with probability $1-\\mathcal E_{k,\\delta}$ by the definition of the excess risk, and if subsamples are approximately independent (e.g, when $k<<n$), the number of subsamples needed to obtain an $\\delta$-optimal model is approximately geometrically distributed with success rate $1-\\mathcal E_{k,\\delta}$. The probability $1-\\mathcal E_{k,\\delta}$ typically does not approach zero exponentially fast as $\\delta\\to 0$, so the required ensemble size does not need to increase exponentially."}, {"review_id": "sI5pPs2dkB", "reviewer": "Reviewer_pCzZ", "summary": "The authors propose a new method for aggregating base learners, each trained on a subsample of the training set. They prove and show for toy examples that the tail probability for the corresponding excess risk can be exponentially small, when the assumptions are met. The empirical performance of the proposed method is also demonstrated.", "questions": "Q1. If $\\eta_{k,\\delta}\\leq0$, what can be said?\n\nQ2. What are the reasonable conditions under which $\\eta_{k,\\delta}>0$?\n\nQ3. In Figs. 1 and 2, can you add the tail probability for bagging?\n\nQ4. In Example 1.1 and/or the linear regression example, can you provide the corresponding tail bound for bagging? Is there any substantial improvement by applying your proposed method?\n\nQ5. In Algorithm 2, can you speficy ``Choose $\\epsilon\\geq 0$ using the data...''?  How is $\\epsilon$ picked practically such that it satisfies the conditions in Theorem C. 11, which seem hard to check? \n\nQ6. In Theorem C.11, it is unclear to me in which ways $k_1,k_2,B_1,B_2$ go to infinity as $n$ goes to infinity, respectively. It seems problematic in some cases. Note that the tail probability on the right-hand side of Eq. (34) is greater than $B_1e^{-B_2/C_3}$. If $B_2=\\Theta(\\log n)$ and $B_1=\\Theta(n^{1+0.01})$, then the bound is trivially going to infinity. How can the left-hand side converge to 0?\n\nQ7. This is a minor comment. In Technical Novelty, the authors mention ``a sharper concentration result for U-statistics with binary kernels, improving upon standard Bernstein-type inequalities.'' I believe the KL divergence type concentration inequality is not new. In D.2, once it comes to the step that $\\tilde \\kappa$ can be viewed as a binomial random variable, the rest is known. The novelty of the work might be the application of this result in U-statistics with binary kernels.", "limitations": "Yes. (I do not foresee any negative societal impact of the work.)", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The proposed method is reasonable and potentially useful when the tail probability needs to be controlled. The results presented in Figs. 1 and 2 are consistent with intuitive expectations.\n\nWeaknesses: \n1) Theoretically, although the authors claim that the performance enhancement of their method is ``agnostic to the underlying base learner,'' the crucial condition that $\\eta_{k,\\delta}>0$ seems hard to verify for a given algorithm $\\mathcal{A}$ and a given $\\delta>0$. If such a condition only holds for extremely large $\\delta$ while the population risk is bounded, then such a result may not be very informative. This scenario is possible. Consider the case of a finite $\\Theta$ for simplicity. Suppose that, for some dataset, the algorithm $\\mathcal{A}$ outputs $\\theta\\in\\Theta$ with roughly the same probability, and for the population risk minimizer $\\theta^\\ast$, we have that $L(\\theta^\\ast)\\ll L(\\theta)$ for all $\\theta\\neq \\theta^\\ast$. Then $p_k^{\\max}\\approx 1/|\\Theta|$, while $\\mathcal{E} \\approx 1 - 1/|\\Theta|$ for a large range of $\\delta$. Then the condition that $\\eta_{k,\\delta}>0$ cannot be satisfied in such a case. (Here $\\mathcal{E}$ denotes $\\mathcal{E}_{k,\\delta}$. There is some unknown reason that this cannot be displayed correctly.) \n2) Also, the condition $\\eta_{k,\\delta}>0$ is unreasonably strong for me. On the one hand, $p_k^\\{\\max}$ is the probability that corresponds to the mode in $\\Theta$. On the other hand, $\\mathcal{E}$ is the tail probability for the excess risk incurred by some random $\\theta$. There is no reason that these two can be compared. By requiring the former be (strictly) greater than the latter, it is qualitatively requiring that the excess risk for the ``mode'' base learner can almost be controlled, which leads to the exponential tail. In my opinion, this is too strong. It is also unsatisfactory that there is no explicit dependence on $\\delta$ in the final expression of the tail bound.  \n3) There are some technical details that might not be totally correct, or need further clarification. (See Questions below.)\n4) Practically, the authors only compare their method with the conventional bagging in terms of the mean test error, rather than the tail probability. I believe it makes much more sense to compare the tail probability with bagging.", "was_revised": true, "final_justification": "The proposed algorithm is practically relevant, and the authors provide theoretical justification under reasonable assumptions. My initial rejection was targeting the unrealistically strong statement in the paper. As the authors have agreed to revise accordingly, I will raise my score. Since reviewers are advised to assign borderline scores sparingly and this year there are only 6 scores in total, I gave the paper a Reject first, but now I change it to an Accept.", "rebuttal": "> **W1:** Hard to verify the condition $\\eta_{k, \\delta}>0$ for a given algorithm $\\mathcal{A}$ and a given $\\delta>0$.\n\n**A:** Although it can be nontrivial to verify the condition since it's not as explicit as moment or structural conditions, we choose not to use more explicit conditions in order to make the theorem lightweight and at the same time convey enough insight regarding the behavior of the algorithm. In particular, the theorem clearly shows the difference our algorithm makes --- our explicit bound (10) clearly demonstrates how the tail $\\mathcal{E}_{k,\\delta}$ of the base learner is improved by the ensemble. We figure that this forms a good balance between technical complexity and the insightfulness of the theorem.\n\n\n> **W2:** Restrictiveness of the condition $\\eta_{k, \\delta}>0$\n\n**A:** Thanks for pointing out this. This condition can be relaxed. We use this more restrictive condition in Theorem 2.1 to streamline the presentation. See Theorem C.8 for the original version of this condition in equation (28), where we compare the global mode of the solution space with the mode among all non-$\\delta$-optimal solution. We can readily replace the condition in Theorem 2.1 with this relaxed condition without affecting its validity. This relaxed condition can be satisfied by the example provided by the reviewer.\n\n> **W4:** Comparing tail probability with bagging\n\n### Percentiles of test performance\n\n- $n=2^{13}$, Pareto shape = $1.1$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|6.35|15.09|31.57|68.878|154.42|381.5|\n|ROVE|1.246|2.837|3.53|4.604|5.342|7.379|\n|ROVEs|1.806|3.042|3.87|4.243|4.649|6.516|\n|Bagging|3.914|7.715|11.952|30.704|41.481|114.48|\n\n- $n=2^{13}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|1.002|2.173|2.911|4.214|5.041|5.21|\n|ROVE|0.668|0.806|0.93|0.984|1.051|1.16|\n|ROVEs|0.699|0.801|0.877|0.978|1.061|1.107|\n|Bagging|0.444|0.561|0.637|0.81|1.621|3.002|\n\n\n> **Q1:** If $\\eta_{k, \\delta} \\leq 0$, what can be said?\n\n**A:** We do not have a bound for tail in this case.\n\n\n\n> **Q5:** In Algorithm 2, can you speficy \"Choose $\\epsilon \\geq 0$ using the data...\"? How is $\\epsilon$ picked practically such that it satisfies the conditions in Theorem C. 11 , which seem hard to check?\n\n**A:** Thank you for the question. It is nontrivial to pick $\\epsilon$ to satisfy the technical condition in Theorem C.11. In practice we use an adaptive strategy for choosing $\\epsilon$. Yet, we deferred that to Appendix F.3 (page 42) because of the space limitation. On a high level, the proposed procedure aims to find an $\\epsilon$ that makes it more likely for the true optimal solution to be included in the \"near optimum set\", instead of being ruled out by suboptimal solutions. We also kindly refer the reviewer to Figures 4, 5, and 8 in Appendix F.3 for more experiments that compare the algorithm performance under various choices of $\\epsilon$. Regardless of potential violation of the conditions, the practical performance of this adaptive strategy is satisfactory.\n\n> **Q6:** Growth rate of $k_1, k_2, B_1, B_2$ to achieve convergence\n\n**A:** The reviewer is correct that $k_1, k_2, B_1, B_2$ need to grow in a certain way to make the bound vanish. The typical scale of these numbers when applying our method is that $k_1,k_2$ are of the same order, $n/k_1\\to \\infty$, $n/k_2\\to\\infty$, and $B_1=O(n/k_1),B_2=O(n/k_2)$.\n\n> **Q7:** In Technical Novelty, the authors mention \"a sharper concentration result for U-statistics with binary kernels, improving upon standard Bernstein-type inequalities.\" I believe the KL divergence type concentration inequality is not new. In D.2, once it comes to the step that $\\tilde{\\kappa}$ can be viewed as a binomial random variable, the rest is known. The novelty of the work might be the application of this result in U-statistics with binary kernels.\n\n**A:** The reviewer is correct about the KL divergence type concentration. The novelty indeed lies in the application of this result in U-statistics with binary kernels."}, {"review_id": "NaWrsgXJDV", "reviewer": "Reviewer_v3Su", "summary": "This paper studies the technique of ensemble learning, a popular paradigm consisting in aggregating several weak learners into a strong model (e.g., combining decision trees into tree ensembles). The authors propose the novel methodology of simply selecting the best base learner out of the pool of models trained on different subsamples of the data. In the easiest case, this happens via majority voting. They show that this improves the generalisation bound of the model, guaranteeing an exponentially decaying generalisation tail even where the general problem has a slow polynomial decay.\n\nMore specifically, in a discrete problem the model appearing more frequently is selected as the output model (MoVE). In continuous problems, this degenerates as all learned models likely appear exactly once. Therefore, ROVE chooses the model that has the highest likelihood of being eps-optimal.\n\nThe authors then formally derive theoretical bounds for the exponentially decaying generalisation tail in both scenarios. \n\nThey then experiment with MoVE and ROVE, which actually comes in two different versions, one where all data is used in both steps, one that splits the data between learning candidate models and performing eps-optimality vote. Experiments are performed on synthetic regression datasets tackled with MLPs, and on four discrete heavy-tailed stochastic programs. For the regression cases the proposed algorithms seem to work better than a single base learner. A further comparison is drawn with bagging - here we see that bagging wins on light tailed, and viceversa, which is reasonable. Performances on the stochastic programs look competitive, and ROVE seems the best alternative.", "questions": "* I'm not entirely sure I get the discrete scenario. The majority vote in MoVE happens over the different trained models. Does that mean multiple models that are exactly the same are the output of the training on different subsamples? e.g., we would need to have two identical decision trees? Or is this for example related to the numerical solution of a stochastic program? Could you please provide a practical example of a discrete scenario? It's probably just a lack of expertise on my side.\n\n* In addition to the formula in the algorithm, could you better explain in a couple of sentences and/or with an example what it means that a model is eps-optimal?\n\n* The proposed method envisions always using one single learner (extracted through majority voting or finding the eps-optimal one), and justifies how this improves generalisation. Intuitively, often using boosting/bagging is a much more powerful solution (e.g. boosted ensembles such as XGB perform way better than single decision trees). Indeed in Figure 2 you show that for light-tailed distributions subagging wins over ROVE. \n     - Is this always the case? Does your method always wins for heavy-tailed distributions?\n     - Were you able to find a \"cutoff\" which tells when your method is preferable, depending on how data is distributed? Can you extract this somehow from the training data?\n    - Have you compared your algorithms to other ensembling techniques other than bagging (from Figure 2)?\n\n* Arguably the most popular type of ensembles in machine learning is tree ensembles. I wonder why no experiments were presented using decision trees? Do you know if your algorithm performs well on those?", "limitations": "The authors address one potential limitation in the last paragraph. The work has no potential negative societal impact.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "STRENGTHS\n\n* significance: ensembling is a very popular technique and studies advancing its applicability are definitely valid to the ML and optimisation communities\n\n* quality: the paper is well written, has a solid theoretical justification and an extended experimental evaluation (I have only one concern that I express in my questions)\n\n* originality: the work is original and seemingly valid for any kind of ensemble - therefore it could lead to practical improvements in diverse areas where current ensembling solutions are not satisfying enough\n\nWEAKNESSES\n\n* the work is quite theoretical and I do not necessarily see an immediate reflection in ML models, e.g., I am still a bit unsure that a single tree can do better than an ensemble in a lot of scenarios. See my related question. \n\n * while I get that the main point is a higher level contribution, it feels a bit weird to me that a paper on ensembles does not have any experiment related to tree ensembles, arguably the most popular ensembling technique in ML - see my related question later", "was_revised": true, "final_justification": "I have appreciated the authors' responses, as they were on point and even included an additional suggested experiment. \nOn the other hand, I do understand some of the weaknesses highlighted by other reviewers and I still somehow question the practical usefulness of this method. \nTherefore I am retaining my original score of borderline accept - but I'm in favour of the paper being accepted if replies to other reviewers will be considered satisfactory enough!", "rebuttal": "Thank you very much for your detailed review and positive feedback. We hope our replies below can provide further clarity and address your concerns. Please feel free to let us know if you have any further question.\n\n\n> **Q3:** The proposed method envisions always using one single learner (extracted through majority voting or finding the eps-optimal one), and justifies how this improves generalisation. Intuitively, often using boosting/bagging is a much more powerful solution (e.g. boosted ensembles such as XGB perform way better than single decision trees). Indeed in Figure 2 you show that for light-tailed distributions subagging wins over ROVE. (1) Is this always the case? Does your method always wins for heavy-tailed distributions? (2) Were you able to find a \"cutoff\" which tells when your method is preferable, depending on how data is distributed? Can you extract this somehow from the training data? (3) Have you compared your algorithms to other ensembling techniques other than bagging (from Figure 2)?\n\n**A:** Thank you for the questions. The goal of our work is to provide a fresh perspective, especially for problems that suffer from heavy-tailed noises, that by performing voting (subsampled ensemble) on the model level instead of the output level, one might be able to achieve better generalization performance. Although the output model from our algorithms is one of the base learners, the main message we want to convey is not that \"a single tree can do better than an ensemble of trees\". Instead, we want to demonstrate that by carefully selecting a model from the candidate sets, one can possibly achieve the generalization performance that a simple aggregation cannot offer (for example, for heavy-tailed problems, a simple average might not effectively reduce the noises).\n\nIn theory, as long as the mild assumptions stated in our theorems are satisfied, our methods are guaranteed to have the exponentially decreasing excess risk tails. This is what other ensemble approaches do not have. Indeed, in our new experiments shown below, our methods outperform all popular ensemble methods in tail performance when the problem gets heavy-tailed.\n\n\n\n> **W2:** Comparison with tree ensembles\n\n**A:**  We have added a new set of experiments comparing our approach with popular existing tree ensembles, including Random Forest (RF), Gradient Boosted Decision Trees (GBDT), and XGBoost (XGB). Decision trees are used as the base learner for all methods. Random forests are constructed with the same number of decision trees as our methods to ensure a fair comparison. GBDT and XGB are constructed with early stopping to avoid overfitting. Results on percentiles of the test errors are as follows:\n\n## Comparison with tree ensembles in terms of tail performance\n### For the same synthetic data as described in lines 209-212\n- $n=2^{11}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|19.664|38.005|81.457|193.69|492.9|2035.014|\n|ROVE|3.455|4.431|4.943|5.569|6.153|6.323|\n|ROVEs|2.309|3.056|3.4|3.978|4.261|4.547|\n|RF|1.016|2.683|4.617|6.5|32.222|210.42|\n|GBDT|0.787|1.825|3.415|6.81|30.019|87.736|\n|XGB|1.635|5.092|9.101|21.094|52.973|105.72|\n\n- $n=2^{11}$, Pareto shape = $2.0$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|2.55|3.436|4.734|6.184|9.825|24.89|\n|ROVE|0.927|1.116|1.238|1.329|1.489|1.604|\n|ROVEs|0.665|0.832|0.907|0.987|1.035|1.094|\n|RF|0.121|0.181|0.249|0.326|0.757|2.789|\n|GBDT|0.114|0.184|0.246|0.324|0.819|1.057|\n|XGB|0.289|0.573|1.082|2.279|3.711|6.764|\n\n\n- $n=2^{11}$, Pareto shape = $2.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|0.845|0.994|1.138|1.315|1.599|2.415|\n|ROVE|0.389|0.448|0.502|0.535|0.62|0.65|\n|ROVEs|0.289|0.353|0.382|0.41|0.431|0.44|\n|RF|0.044|0.053|0.062|0.073|0.102|0.189|\n|GBDT|0.043|0.06|0.074|0.087|0.105|0.116|\n|XGB|0.103|0.173|0.248|0.421|0.588|0.913|\n\n\n### For a new synthetic data $Y=10\\sum_{i=0}^{9}2^{-i}\\sin(2\\pi X_i)+\\epsilon_1-\\epsilon_2$ where each $X_i$ is uniform on $[0,2]$ and $\\epsilon_1,\\epsilon_2$ are Pareto\n\n- $n=2^{15}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|46.095|103.303|193.074|364.772|640.562|1287.311|\n|ROVE|17.683|18.981|19.483|20.908|21.484|22.072|\n|ROVEs|17.907|19.262|20.444|21.171|21.715|23.893|\n|RF|6.518|10.507|18.519|34.58|46.284|79.079|\n|GBDT|21.61|40.734|59.422|87.771|136.325|232.915|\n|XGB|31.989|46.385|72.751|207.12|496.714|596.137|\n\n\n\n- $n=2^{15}$, Pareto shape = $2.0$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|6.341|7.251|7.924|9.374|12.617|18.885|\n|ROVE|8.975|9.248|9.413|9.501|9.563|9.683|\n|ROVEs|10.95|11.299|11.506|11.602|11.706|11.821|\n|RF|4.18|4.274|4.322|4.477|4.583|4.742|\n|GBDT|2.699|4.052|6.68|9.019|12.409|18.297|\n|XGB|5.77|8.136|10.154|13.496|17.501|28.473|\n\n### For a new synthetic data $Y=10\\sin(2\\pi X)+\\epsilon_1-\\epsilon_2$ where each $X$ is uniform on $[0,2]$ and $\\epsilon_1,\\epsilon_2$ are Pareto\n\n- $n=2^{15}$, Pareto shape = $1.5$\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|35.753|84.013|149.819|267.985|423.76|665.424|\n|ROVE|5.969|7.133|7.808|8.481|9.272|9.704|\n|ROVEs|4.633|5.347|5.902|7.043|7.916|10.408|\n|RF|2.967|7.792|14.225|22.411|36.374|62.494|\n|GBDT|6.247|15.913|31.117|50.551|72.74|178.967|\n|XGB|3.636|6.206|8.579|13.917|25.043|27.09|\n\n- $n=2^{15}$, Pareto shape = $2.0$\n\n\n||50%|80%|90%|95%|97.5%|99%|\n|-|-|-|-|-|-|-|\n|base|1.944|2.579|3.479|4.35|5.367|7.477|\n|ROVE|0.889|0.997|1.065|1.11|1.149|1.264|\n|ROVEs|0.726|0.824|0.874|0.936|1.023|1.049|\n|RF|0.165|0.245|0.307|0.377|0.529|0.637|\n|GBDT|0.732|0.924|1.129|1.431|1.659|2.511|\n|XGB|0.331|0.443|0.568|0.687|0.875|1.007|\n\n\nThese results show that our methods outperform the base learner in almost all cases, and also outperforms RF, GBDT, and XGB especially in high percentiles when the tail is heavy (e.g., with Pareto shape 1.5). For not so heavy-tailed cases RF, GBDT, XGB may outperform our methods.\n\n> **Q1:** I'm not entirely sure I get the discrete scenario. The majority vote in MoVE happens over the different trained models. Does that mean multiple models that are exactly the same are the output of the training on different subsamples? e.g., we would need to have two identical decision trees? Or is this for example related to the numerical solution of a stochastic program? Could you please provide a practical example of a discrete scenario? It's probably just a lack of expertise on my side.\n\n**A:** We are certainly happy to provide more clarifications. A discrete scenario refers to problems where the decision space consists of discrete solutions. In such cases, when solving the same problem on multiple subsamples, some solutions may appear repeatedly across different base learners. In the machine learning context, a good example is model selection where one selects a final model among finitely many candidates. It indeed more naturally arises in stochastic programming with discrete solution space.\n\n\n> **Q2:** In addition to the formula in the algorithm, could you better explain in a couple of sentences and/or with an example what it means that a model is eps-optimal?\n\n**A:** No problem! In general, a solution $\\theta$ is called $\\epsilon$-optimal for the optimization problem $\\min_{\\theta\\in\\Theta} L(\\theta)$ if its loss satisfies $L(\\theta) \\leq L(\\theta^\\star) + \\epsilon$, where $\\theta^\\star$ is the true optimal solution. \n\nIn the specific context of Algorithm 2 (ROVE/ROVEs), a solution $\\theta$ is considered $\\epsilon$-optimal on a given subsample if, when evaluted on that subsample, its loss is within $\\epsilon$ of the best loss achieved on that subsample. For each subsample, Phase II of Algorithm 2 basically finds all such $\\epsilon$-optimal solutions among the retrieved solutions. Finally, the algorithm selects the solution that is $\\epsilon$-optimal for the largest number of subsamples. This procedure can be viewed as a generalized majority vote in the continuous space."}]

Author rebuttal:

Meta-review: The authors present a new perspective on building ensemble models. The authors argue that, in the presence of heavy tail noise, it is beneficial to "ensemble" the models rather than the outputs. They propose training models on multiple subsamples of the training data (just like a normal ensemble), but, rather that averaging the predictions of these models, one should just pick the single base learner that was most often obtained (thus the final model output by the procedure is not actually an ensemble in the classical sense, but a single base model).  The authors provide a comprehensive theoretical treatment of the problem, and provide experiments on synthetic data supporting the theory.  After the discussion with the authors all reviewers recommend accepting the paper provided that the authors revise the paper to address their concerns.   

In addition, I would like to highlight one shortcoming of the paper that received less attention from the reviewers: the lack of empirical evaluation on real data. In the rebuttal the authors show limited results on real problem and without comparing to ensemble based methods like bagging and random forests.  While I appreciate that the main contribution of this paper is theoretical, it would be greatly strengthened the paper if the authors would showcase the practicality of their approach by tackling more realistic problems.  Since, as the authors claim, optimization with heavy tailed noises has received significant attention in various fields, there should be ample opportunity to apply the proposed technique on real data from finance, scheduling or physics. I strongly encourage the authors to do so.
Decision: Accept (poster)