Robust Minimax Boosting with Performance Guarantees
Authors: Santiago Mazuelas
Veronica Alvarez
Venue: NeurIPS 2025 poster ()
Keywords: boosting
robust methods
label noise
performance guarantees
supervised classification
Primary area: theory
TL;DR: This paper presents methods for robust minimax boosting (RMBoost) that minimize worst-case error probabilities, are robust to general types of label noise, and provide finite-sample performance guarantees with label noise

Abstract: Boosting methods often achieve excellent classification accuracy, but can experience notable performance degradation in the presence of label noise. Existing robust methods for boosting provide theoretical robustness guarantees for certain types of label noise, and can 
exhibit only moderate performance degradation. However, previous theoretical results do not account for realistic types of noise and finite training sizes, and existing robust methods can provide unsatisfactory accuracies, even without noise. This paper presents methods for robust minimax boosting (RMBoost) that minimize worst-case error probabilities and are robust to general types of label noise. In addition, we provide finite-sample performance guarantees for RMBoost with respect to the error obtained without noise and with respect to the best possible error (Bayes risk). The experimental results corroborate that RMBoost is not only resilient to label noise but can also provide strong classification accuracy.

Robust Minimax Boosting with Performance Guarantees
Santiago Mazuelas Verónica 2lvarez Basque Center of Applied Mathematics (BCAM) Massachussets Institute of Technology (MIT) "IKERBASQUE-Bagpe Basque Foundation for Science smazuelas@bcamathee org, veal vealvarmmit. edu
Abstract
Boosting methods often achieve excellent classification accuracy, but can experi- ence notable performance degradation in the presence of label noise. Existing robust methods for boosting provide theoretical robustness guarantees for cer- tain types of label noise, and can exhibit only moderate performance degradation. However, previous theoretical results do not account for realistic types of noise and finite training sizes, and existing robust methods can provide unsatisfactory accuracies, even without noise. This paper presents methods for robust minimax boosting (RMBoost) that minimize worst-case error probabilities and are robust to general types of label noise. addition, we provide finite-sample performance guarantees for RMBoost with respect to the error obtained without noise and with respect to the best possible error (Bayes risk). The experimental results corrobo- rate that RMBoost is not only resilient to label noise but can also provide strong classification accuracy.
Introduction
Boosting methods provide excellent predictive performance numerous practical scenarios (see e.g.. (I). These methods determine linear combination of base-rules through a sequential opti- convex poten- tial). After the introduction of AdaBoost in (2), multiple boosting methods have been presented (3] together with highly-efficient implementations [4] ()). Unfortunately, it has been widely observed that the performance of boosting methods can be significantly affected by the presence of label noise (see e.g., (68)). Certain boosting methods such as LogitBoost and GentleBoost provide an improved resilience noise by using alternative convex potentials or optimization approaches [ However, as shown in [10], any boosting method that minimizes empirical averages of convex and bounded potential can lead poor performances in the presence of label noise (even if only a very small portion of labels are incorrect). Such result posed a serious concern on boosting methods, as label noise is often unavoidable practice and its extent typically hard quantify. For instance, in cases where an adversary intentionally modifies some labels, the machine learning practitioner may be entirely unaware of the resulting noise in the training data.
mization process that minimizes certain functional (often the empirical average
Multiple alternative boosting methods have been proposed to bypass the negative result of Long and Servedio in [10] by minimizing empirical averages of non-convex unbounded potentials IT-- 15). These robust methods can result in performances that are only mildly affected by label noise. Notably, previous theoretical results show that methods based on specific potentials (c.g.. unhinged, quadratic, and sigmoid) are provably robust to certain types of label noise [13H]5]. Specifically, the accuracy of these methods is not degraded by symmetric and uniform label noise for large enough training sizes. However, previous theoretical results do not show how the performance of boosting
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

methods is affected by more realistic types of label noise and finite training sizes. In addition, existing robust methods do not provide theoretical guarantees with respect to the best possible error (Bayes risk). Indeed, certain robust methods have shown to achieve unsatisfactory classification performance 13 [6], since their accuracy can be low even without noise.
This paper presents robust minimax boosting (RMBoost) methods that eliminate the need to select a potential function by directly minimizing worst-case error probabilities. Our results demonstrate that RMBoost is robust to general types of label noise with finite training sizes, and can also provide strong classification performance. The main contributions presented in the paper are as follows.
We show how RMBoost rules can be learned by solving a linear optimization problem with optimum value that corresponds to RMBoost minimax risk.
We provide finite-sample performance guarantees for RMBoost with respect to the error obtained without noise and with respect the Bayes risk.
We present efficient algorithms for R.Mooot learning that greedily obtain a sequence of linear combinations of base-rules with decreasing minimax risks.
The experiments show that RMBoost can outperform existing methods in the presence of noisy labels and also achieve strong classification accuracies without noise.
Calligraphic letters represent sets; bold lowercase letters represent vectors; sign(-) de- notes the sign of its argument: || || and || I| denote the 1-norm and the infinity norm of its argument, respectively; ( (-)+ and [-] denote the positive part and the transpose of its argument, respectively: 1 denotes the vector with all components equal to I; < and 2 denote vector incqual- ities; and Ep } and Varp } denote, respectively, the expectation and variance of its argument with respect to distribution p.
Notations:
2
Preliminaries
This section first recalls the setting for boosting methods and states the notation used in the paper. Then, further describe related methods and results.
2.1 Problem formulation
Classification rules assign instances in a Borel set X' C Rd with labels in finite set y. As is com- monly done in the boosting literature, in the following we consider binary classification problems, i.e., y = +11. We denote by A(X x )") the set of probability distributions on X' 3 en- dowed with suitable sigma-algebra, while the set of classification rules (both deterministic and randomized) is denoted by T)) For p A y). we denote by Pa E A(X) the marginal distribution over X' and by p(ylar) the conditional probability of label y E ) given x E X. For a classification rule h E T(X', ))), we denote by h(y x) the probability with which instance
X is assigned the label y E y (note that h(ylz) E (0. 1) if h is a deterministic rule). With a slight abuse of notation we denote by h(z) the label assignment provided by the rule for instance x, which is random variable if h is a randomized classifier.
Supervised classification methods use training samples to obtain classification rule h with small error probability R(h), referred to as risk. p" E A(Y' x )) is the underlying distribution of instance-label pairs, the error probability of a classification rule h E T(X, V) is its expected ()-1 loss, that is, R(h) = Ep- (fo- (b, (I, y))}. where
(h, (x, v)) P(h(x)) + w) = h()la))
is the 0-1 loss rule h at instance-label pair (x, v/)
The n training samples (11,31), (I2, U2),.... .., ..., (In,
yn) available for learning may be affected by label noise. We consider general types of label noise, namely, for each instance x E X' the la- bel is flipped to -y with a probability 0 < (z) < 1 for which no assumptions are imposed. Noise-less cases correspond to (+1(x) p-1 = A z E X, symmetric noise corresponds to (+) = p- (x) V x E X and uniform noise corresponds to (x) P,y('') V x, E &X y y. In practice, is expected that the noise probabilities of most instances are rather small or zero, while those of other instances are non-negligible and unknown.
2

---

The label noise considered in the paper covers arbitrary forms of label corruption in the training samples. In particular. the results in the paper even account for deliberate manipulations of labels, where an adversary may consistently modify the labels of specific instances (p+1 (ar) or p=)(x) may be 1 for certain instances x E X' that the adversary deems most influential to learning). With noisy labels, the distribution of training samples p" E A x ))) is different to the underlying distribution p". Specifically,, the marginals coincide p = Pa while the label conditionals satisty
p'(vlz) = (1 (,(x))) (vlx) + P-u(2)p"
(2)
Boosting methods obtain classification rules given by combinations of base-rules in a set H = {Ri, ..,.... } C VY) The set of base-rules considered often contains an extremely large number T of simple rules, e.g., all the decision trees with a bounded number of nodes given by components of instances in the training set. Often, base-rules are themselves classification rules, i... f(z) E { for any X. We only assume the common case in which the base-rules are bounded measurable functions h(z)= E [-1, 1] for any x E X, and that - - E H. if h E H.
2.2 Related work
Most of boosting methods can be interpreted as empirical risk minimization (ERM) techniques that learn classification rules by solving the optimization problem
1 n
min
(vrt((z)) 14)
where the vector h(z) (f1) h2(z), ... hr(=))))..,,, is given by predictions of the base-rules in H. Then, the classification rule is given by h(z) = sign(h(z) 1²) with μ² a solution of (3). The function o--) in (3) is referred to as potential function and its argument y,h(z;)) I is re- ferred to as the margin of sample (z,, y1) for parameters μ (see e.g.. (6). Each potential function gives rise to a different boosting method (see e.g., B (). For instance, AdaBoost corresponds to the potential function <b2) = exp(-z), and LogitBoost corresponds to the potential function <(=)= = log(1 + exp(-2)). In particular, the resilience to noise of LogitBoost is attributed to the lower values taken by the logistic potential for < O.
The results in 100 showed that even a very small fraction of noisy labels can lead to poor performances using any convex and bounded potential (i.e., d(2) convex, d'(0)
and lim,-+x ((z) = 0). Multiple methods have been proposed to bypass the negative result in [TO] by using non-convex or unbounded potentials, such as the sigmoid potential 6(2) = (1 + exp(2))
the quadratic potential 6(z) (1 (1-2) 2)², and the unhinged potential Ø(2) = 1 - 2. These potential functions have been shown to result in methods that are robust to noise the sense that the corre- sponding optimization 33 is not affected by symmetric and uniform label noise for large enough training sizes [3 17 Specifically, for some potentials including sigmoid and unhinged, the expected potential with symmetric and uniform noise is proportional to that without noise [14). For the quadratic potential, minimizers of the expected potential with symmetric and uniform noise are equivalent to those without noise [7]. On the other hand, it has been shown that such potential functions can lead to poor classification performances, even without noise [6].
The existing robustness results do not show how the performance is affected by more realistic types of noise and finite training sizes. Only the results in [4] go beyond symmetric and uniform cases and provide certain extensions of the above-described results to cases with symmetic non-uniform noise (p+1 (z) (z) varying with x). Furthermore, existing robustness results do not provide finite-sample generalization guarantees since they analyze the potential's actual expectation, not cases with empirical averages. In boosting methods, results for finite-sample empirical averages cannot be derived from those for actual expectations because performance bounds based on the convergence of the potential averages are inadequate for boosting (see e.g., Sec. 4.1 in (6).
The following presents boosting methods that avoid the need to select a potential function by directly minimizing worst-case error probabilities.
3

---

3
Minimax boosting
RMBoost methods learn classification rules by solving the minimax problem
min max Ep (o, (0,v)))-
(4)
bET(N))) PEu
Such optimization considers general classification rules [(x,)) probability distributions in subset C A(X x )) referred to as uncertainty set, and expected 0-1 losses (i.c., error probabili- ties). Minimax approaches such as that in 4 are commonly known robust risk minimization or distributionally robust techniques [2 Unlike an ERM approach, the optimization in ! con- siders multiple distributions beyond the empirical distribution of training samples, so that RMBoost methods can achieve enhanced robustness as shown in the following. In addition, the optimal value of 4 referred to as the minimax risk R can be used to assess R.Booos classification error.
Unlike other distributionally robust methods, RMBoost considers uncertainty sets defined by the set of base-rules H. Specifically, the uncertainty set of distributions U in 4 is given by the training samples and the base-rules H. as
u = {o EAAE x )) s.t. | (yt((x) -
1 Σ vi (ntt(())l 5n}
(5)
where the vector h(z) = 11 (I),,
is given by the predictions of base-rules in H. in B.. The parameter À O accounts for the error in the finite-sample average in (5) and can be selected using standard cross cross-validation approaches. This selection can be enhanced taking into account the family of base-rules used or prior knowledge on the amount of label noise. In particular, more complex families of base-rules or increased levels of noise can benefit from higher values for x. A simple default value for such parameter is 1/V7, which is the value used in all the experimental results in the paper (Appendix H.5) further analyzes the sensitivity of the proposed methods the choice of that hyperparameter)).
The uncertainty set in 5 comprises probability distributions over instance-label pairs that are sim- ilar to the empirical distribution of training samples, is commonly done in distributionally bust methods. While most existing methods define this similarity in terms of metrics such as the Kullback-Leibe Leibler divergence or the Wasserstein distance (18), the proposed approach defines sim- ilarity in terms of the set of base-rules considered (e.g., the set of decision trees with / decision nodes). Specifically, two distributions are regarded similar if, for any base-rule h E H. the ex- pected value of yh(x:) changes only slightly when computed under either distribution. This notion of similarity offers two key advantages: it can yield quite restricted uncertainty sets (since common sets of base-rules are fairly expressive), and provides strong theoretical guarantees (since common sets of base-rules facilitate the fast and uniform convergence of empirical expectations).
The minimax formulation in (4) followed by RMBoost methods is particularly suitable to obtain robust classification rules since it minimizes worst-case error probabilities. However, the minimax problem in 4 may seem to be computationally prohibitive in practice. The next result shows that RMBoost classification rules can be obtained by solving the convex optimization problem
1
min F(u) =
2 T 4 + N||||||1
(6)
P
1 コ = h(x) 4 u 5. Ve E X.
s.t.
Theorem 1. If μz is a solution of 6 the classification rule hn T(XX)) given by
h (ylx:) yh(x:) 40" + 1/2
is solution of the minimax problem in 4 In addition, the minimax risk R coincides with the optimum of (6, that is R F.
Proof. See Appendix C

---

The result above shows that the minimax problem in 4 is equivalent to the convex optimization problem in ( This equivalence not only provides tractable formulation for RMBoost learning but also enables the interpretation of RMBoost methods in terms of margins. In particular, the formulation in K reveals that RMBoost maximizes the average margin while enforeing both upper and lower margin constraints. As result of these constraints, an increased average margin leads to an overall increase in the distribution of margins (an average margin near 1/2 pushes all the margins to be near 1/2), In contrast, methods that only aim to maximize the average margin may result in instances with very low margins since others are allowed to have large margins. Hence, in existing methods the average margin is often maximized while simultaneously minimizing the margin variance [23] Other methods such as LPBoost [25] and Are-Gv [26] that maximize the minimum margin often lead to poor classification performance since they only account for the minimum margin and not for the distribution of margins [27.. The interpretation of RMBoost in terms of margins also provides further insights for its robustness noise. In conventional boosting methods, a sample with an incorrect label can highly impact the learning process if its margin takes large negative value because it would result in large potential value in (3) For methods based on quadratic or unhinged potentials, even samples with large positive margins can significantly impact the learning process because they would also result in large potential values. Such type of effects are not present in the methods proposed because the margins are bounded due to the constraints in the optimization problem (6)
[heorem[]show that the classification rule with the minimum worst-case error probability is given by linear combination of base-rules. This minimax classification rule can be learned by solving the optimization (6). which carries out an L. L.lrregularization (term X \|]xa[|1) leading to a sparse com- bination of base-rules. The methods proposed in (8 also minimize worst-case error probabilities using a combination of base-rules. However, such work considers a transductive scenario and aims to combine reduced set of base-rules using prior knowledge of their classification errors.
The classification rule hy-- that minimizes the worst-case error probability randomly assigns labels with probabilities given by the predictions of base-rules, as shown in 7 Similarly to other methods (e.g.. PAC-Bayes techniques (29)), it is often preferred in practice to use the corresponding deter- ministic classifier denoted by by which assigns the label corresponding to the highest probability, i.e., h (2) sign(h(=) p²)). The error probability of the deterministic classifier is ensured to satisfy R(b)--) S 2R(h,-) ) (see c.g., 19 29] ) and often satisfies R(b I R(b,-)) in practice.
Efficient learning algorithms for RMBoost can be developed by leveraging general-purpose opti- mization techniques. Using as variables the positive and negative parts of μ., the optimization prob- lem (6) is equivalent to a linear program that often has sparse solutions, as described above. There- fore, highly efficient algorithms for large-scale linear optimization can be utilized for RMBoost learning. In particular, Section 5 presents
efficient learning algorithm that address (6) using column generation methods. In addition, we next show that RMBoost does not require to solve the optimization in (6) with high accuracy, for instance the presented methods only need that the expected constraint violation in (6 is small.
As described above, the formulation of RMBoost by means of the optimization problem c enables to develop effective learning algorithms and also to interpret RMBoost methods in terms of margins. As shown in the following, the equivalent formulation of R.Boost in (4) as minimax method enables to obtain performance guarantees for general types of label noise.
4 Generalization and robustness guarantees
This section characterizes RMBoost generalization performance with respect the performance obtained without noise and the best possible error probability.
As shown in [ the classification rule given by 7 minimizes the worst-case error probabil- ity if the parameter f4" is a solution of (6). Any other μ can be similarly used to define classification rules as
(1)(2) = y1((2)) T 4 + 2.:2 hy = sign(H(s)T (w)
(8)
where [1]] denotes the clip function [=]] = (min(2, 1))+
5

---

The usage of efficient optimization algorithms for (6 can lead to suboptimal solutions that result in value larger than the minimax risk R or fail to satisfy all the constraints. We say that la is an Sop-SSouuionn of (6) if the sum of the value suboptimality and the expected constraint violation is at most Copt. that is
(F(u) (F( + Epp (h(()) ml - 2
Eopt-
The next theorem provides generalization bounds for RMBoost with respect to the error obtained by an ideal RMBoost learned without label noise and with infinite training samples.
Theorem 2. Let Panise be the probability with which a label is incorrect at training, i.c. Punise ppp (py(2)) and Eest be a bound for the concentration of training averages of base-rules, that is
1 T2 n2
Ep [yh(x))
Σ sh((xs) S Eea, Vh E H.
(10)
If μu is an Oopr-ptiimll solution of d corresponding to training samples, and M4 is an exact solution of (6) using the exact expectation without noise Ep- (yh((z) instead of (1/n) Ei= y.f((;;) Then, we have
R(h,) S R(hn,, + Copt + (Cest + Proise A)]l Molli-
(11)
In addition, if Paoise < 1/2, we have
R(hp) S R(hp.) +
Copt
Eest + 2/ Varp- (py(x)) +
11 Molla-
(12)
2P 2
1 2Pnoise noise
Proof. See Appendix D
The result above shows how RMBoost error is affected by the usage of: training samples with noisy labels (P (P finite training sizes (Eea), and suboptimal learning algorithmms (Eopt). The probability Pmoise = Epp (p)(x) is rather small in common situations where most of the training labels are correct. The error term Eest due the finite number of training samples
be bounded with high- probability using conventional concentration bounds (see e.g., (0)) In particular, if R and D are, respectively, the Rademacher complexity and VC dimension of the family of base-rules H. with probability at least 1 - we have
log2/4 2/5 2n
2D log(3n/D)
log 2/5 2n
Eest S 2R +
2
(13)
so that the sample error Eest generally decreases with the training size at rate O(v (logn)/n.. The етгог term Eopt remains small when appropriate algorithms for large-scale linear optimization are employed. Although problem
④ involves large number of constraints, small expected constraint violations are sufficient to ensure a low Eopt. In particular, the algorithm presented in the next Section achieves sm of order (1 n)/n) by solving sequence of low-dimensional linear programs.
The bound in 12 further describes how RMBoost error is affected by the non-uniformity and asym- metry of the label noise. In particular, in cases with uniform and symmetric label noise have Varp- (Py(z)) = O, so that the bound (12) shows that RMBoost is robust to uniform and symmetric label noise. Specifically, the error of RMBoost is not affected by the presence of uniform and sym- metric label noise for a large enough training size (in that case, Eopt. Eests and À can be taken to be much smaller than 1 2
Differently from existing results, Theorem 2 provides performance bounds that account for finite training sizes and describe the effect of general types of label noise, including the effect due to deviations from uniform and symmetric cases (term Varp- (p)(2))). The next result provides per- formance guarantees for RoBo in terms of the best possible error (Bayes risk).

---

Theorem 3. Let hBayes be the Bayes rule and Un be parameter that satisfies
sup ZEN
Baaye (r) - 2h(x) PB S
Cupprox-
(14)
If is Eopr optimall solution of (6) corresponding training samples possibly affected by noise, we have
R(bn)= S R(hBaays) + Sopt + Eapprox + (Eest + noisee + x)( Mulli 1 + +1lpgll1)
(15)
Proof. See Appendix
The result above shows that RMBoost error probability can be near the best possible performance. In particular, the bound in 13) shows that RMBoost methods are Bayes consistent cases where combinations of base-rules can accurately approximate the Bayes rule, i.e., Eappexx = 0. Such an assumption is also required to achieve consistency with other boosting methods, AdaBoost [31 32), and is satisfied using common families of base-rules. For instance, any measurable function in IR can be accurately approximated using trees with d + terminal nodes [31]
The results presented in this section show that RMBoost is both robust to general label noise and capable of providing near-optimal performance in common situations. The next section presents efficient algorithms for RMBoost learning.
5 Efficient sequential learning for RMBoost
The learning stage of RMBoost obtains parameters μ by (approximately) solving the linear optimiza- tion problem (6) As described above, general-purposs techniques for large-scale linear optimization can be borrowed for RMBoost learning, and the following presents an efficient algorithm based on column generation methods (see e.g., (33)). These methods sequentially increase the number of variables considered and are specially effective for large-scale linear optimization since they can maintain reduced number of variables and exploit warm-starts.
5.1 Learning algorithm
Algorithm [ details the pseudocode of the presented algorithm that learns base-rules fú, fi2,.... hr E H. RMBoost parameters fx' E R', and the corresponding minimax risk R. As other boosting methods, the algorithm greedily selects base-rules multiple rounds.
At each round 1: E 21. K}. the algorithm uses a base learner to select a new base-rule that best fits a set of weighted samples obtained from the training samples (Step in the algorithm). Then, the coefficients for the current set of selected base-rules and the weighted samples for the next round are obtained by solving the linear optimization problem (T6) (Step in the algorithm).
particular, the primal solution provides the coefficients for them minimax rule, the dual solution provides the next round weights, and the optimal value provides the worst-case error probability (minimax risk).
1 Σ you: (u+ -4_ A (u+ + }
max 7 11-11 1--1((a (1-11(aa + +3) a, 2
min 24
i=1
- < u: (u+ - -w_) 1
-ss v ( 33--/m/ y/nn SA
s.t.
2
2
14 E th 14 2 _0 2 0
a. E R", a > 2 0,3
for 1, ...
(16)
for = 1,2, ..,
(17)
where vectors u: E Ree for = 1,2 n are given by [M (k) (xi), 112 (x:), vectors V E Rn for j = 1,2, ..., lu are given by V [hg (k) (zI), n1 (12)
(x:))
(I..)]
(A) = [1[a] (k) (k)
(1))) } are the la base-rules selected at round k and vector y E Rd is given
by [vi U2. V2....,.. yn
The new base-rule selected at each round (column generated in the primal) corresponds to violated dual constraint. Specifically, each base-rule h E H corresponds to the dual constraints
- < [}(z)), M(x2). ... h(x)))(a 3 -ynn) s A.
7

---

Hence, the most violated constraint corresponds to the base-rule that achieves
withh(z;))
min
wrz)h((x.)
(18)
BEH
NEH
where the weights {wi}i=1 ) and labels (0r are given by
3/ 72
(a, (a.- 3.) T = sign
V/ n (a; - (o)-).)).
W/
(19)
Similarly to other boosting methods, (8) is addressed by using a base learner that returns a base-rule with small training error for samples (I,, B45 and weights wy, for i =
Computational cost: Algorithm[aaas running time and memory requirements that can be directly com- pared with existing boosting methods based col- umn generation. The complexity of Algorithm is very similar to that of LPBoost 25 that also solves a linear optimization problem. Specifically, Algo- rithm [ solves in each round linear program with 2t, variables and 2(tx + n) constraints for ty the round k, while LPBoost solves in each round a linear program with n + & variables and 2n + is constraints 225 In addition, the complexity of Algorithm [ is lower than other methods based on column generation [4 36] that address more complicated optimization problems at each round. The complexity per round Algo- rithm D is higher than methods such as AdaBoost or LogitBoost that do not require to solve an opti- mization problem in each round. However, the al- gorithm presented can solve such optimization prob- lems very efficiently by leveraging the properties of column generation methods for linear problems. In particular, the previous solution can provide valid warm-start (basic feasible solution), and previously selected base-rules can be safely removed if they cor- respond with strictly satisfied dual constraints [33] The experiments in Appendix [ further show that the running times of the presented method are com- parable to those of existing techniques.
Algorithm 1 RMBoost learning algorithm
Input: Training samples (:)=)))) parameters X, K Output: μ E R,, hi. li2...., Rig, R
1: 0 < (o) 1/2, w t 1/n, ÿ t- y
2: for k 1,2..., K do
number of base-rules
3: h + BaseLearner (H, {ai, Iti wi)
4: (() + (((--)
5: If Σ w.(hh((;;)) s X BREAK for
6: Add to 7((5) the basc-rule A/4 + h
and assign zero enefficient Solve 16) (warm-start, f4 PA.
7:
8:
4 =__ <- solution primal
9:
a. B < solution dual
10:
R(k) optimal value
11:
(a) 14 14_
12:
w + ly/n (ax (3)-))
13:
y <- sign(y/n (ax (3)
14:
for 1, 2....... .....
(h) do
15:
if u. w (xx) < À then
16:
remove n::0 from ((()) 17: R - R(0, p + p (6) {h.} + (n!*)) (
5.2 Theoretical analysis
The next result provides performance guarantees for the sequence of classification rules determined by I
Theorem 4. Let (k) and R(k) be the parameter and minimax risk determined by Algorithm [ at round k. With probability least 1 - 8, the error probability of the RMBoost rule at the k-th round satisfies
R(hnes)) < (k)) + e(ō) + (Eest + Pnniee-
X) (1
(20)
where E(0) 0 if || (1)1/1 S 1/2, and for (89 |/2 > 16), is given by
2D (og(3n/DD) (11 11 1
log(1/8)
< = 2 (k) ||a
(21)
2n
for D the VC-dimension of the base-rules H. In addition, if Algorithm stops at round k in Step and the base learner accurately solves (18), then (*) is an opp)ompt solution of optimization 6
Proof. See Appendix F
8

---

Table 1: Average classification emrrr in % 1 standard deviation for RMBoost and state-of-the-art methods.
The right sub-table shows cases affected by uniform and symmetric label noise with Paase 10%.
Dataset
AdaB
LogitB
XGB-Q
RMB
Minmax
AdaB
LogitB
XGB-Q
RMB
Minmax
Titanic
2023.22
21:3.77
21:3.77
2243.55
20.0.3
22:14.1
23.
224:3.9
22:13.6
24:0..8
German
24
2444.5
25+334
274:288
26:0..6
30+44.2
4,4
27+-4.1
27+5500
29++0.8
Blood
24.4..4
27:44.3
22:3.99
20.15.4
2.60.6
27::3.9
28:
231:3.4
22:13.9
28:10.9
Credit
14::3.9
14::4.0
22:15.6
14::5.6
16410.4
1814.5
19::4.5
241:4.8
1613.8
21:00.8
Diabet
27=4.99
26:
3444.66
26:
25=0.8
31::5.2
29=5.11
341:4.5
27::5.11
28:1111
Raisin
15::2.7
15::.66
1643.8
12::3.6
1.:1.66
19::3.9
19:44.1
20::3.4
14
19:1.00
QSAR
14+3.11
14+3.11
23+
15+3.11
17+0.5
1943355
18+
26
20+33.3
23++0.8
Climat
8,542.00
8.542.0
8.442.0
7.512.0
9.340.4
124:2.8
1042.9
10::3.2
9.5122.8
1540.88
The result above shows that the error of RMBoost rules Iearned by Algorithm i bounded by the minimax risk obtained in each round (R(*)) together with terms that account for optimization and estimation errors (E(ō) and Eeu) well as the effect of noisy labels (misse). Due to the bound (I3) the two terms due to optimization and estimation errors decrease with the number of samples as O( O(V (log and increase with the VC-dimension of the set of base rules H. Notice that the VC-dimension of decision trees can be bounded as D I (2t + 1) log, (d + 2) for t the number of decision nodes, and d the instances' dimensionality (see e.g.. (37)) leading to bounds of order O( / (t log cl log n))n).
For other boosting methods like AdaBoost, the performance bounds that rely on VC-dimension arguments, exhibit a similar dependence on the number of samples and the VC-dimension, but increase with the number of boosting rounds (see Section 4. (6). Interestingly, the bound in (20) for RMBoost grows with (()x || which can be significantly smaller than the number of rounds due to the L1 Ll-regularization imposed by À > 0.
J describes the performance guarantees of RMBoost rules determined by Algorithm in terms of the results presented in Section In particular, all the results in that section can be directly applied by plugging in =6)) Eapt in cases where Algorithm [ stops in Step 5. For general cases, Appendix shows that the suboptimality of Algorithm increased by term that accounts for possible early termination and for the suboptimality of the base learner in practice.
The performance guarantees presented above reliably represent RMBoost error in practice. In par- ticular, the experimental results below show that the minimax risk R obtained by Algorithm D can serve to assess RMBoost prediction error.
Numerical results
The experiments compare the classification performance obtained by RMBoost with that of 8 boost- ing methods: the 4 state-of-the-art techniques AdaBoost 22]. LogitBoost B. GentleBoost (Р] and
LPBoost [25] together with the 4 robust methods RobustBoost [2]. BrownBoost (11), XGBoost [ with quadratic potential (XGB- Quad), and Cobust-GBDD (88, which are specifically designed for scenarios with noisy labels. Multiple cases of label noise evaluated using the conventional sym- metric and uniform label noise ( (Vx, (+) = (=) (x)) Pnoise), and also using an adversarial type of label noise (py(x)
for the P Finis--faction of training samples with the largest margin, Py(2) = 0 for the other samples). This adversarial noise corresponds to label corruptions designed to maximally hinder learning by altering the most influential samples.
Due to the extensive thcoretical results presented, this section remains necessarily concise. The code implementing the methods presented and reproducing the experiments can be found at https://github
Machi www.aaaaraianna///aaaaaaa..o Neurr 2025 The supplementary materials provide additional details and results in Appendix HH including running times assessments and the results of all the boosting methods in all label noise cases.
Table I shows the classification error achieved by the most representative methods with 8 common datasets noiseless cases and with symmetric and uniform label noise. The results in the table show that RMBoost can obtain state-of-the-art performance in noiseless situations and provide improved

---

AdaBoost uniform and symmetric noise
L.Boost
AdaBoost adversarial noise
Robau-GBDD GBDTT
RMBeod uniform and symmetric noise
Ranking without naise
XGB Quad
RobustBonst
Clasification [9c
RMBoost adversarial noise
BrownBoost
GentleBonst
I LogisBoost
20
RMBoost
AdaBoooi
15
Error with noise error without noise [%)
Noisc probability Packe [8]
Figure Trade-off classification performance ro- bustness to noise the 8 datasets (uniform and sym- metric noise with mosse 10%).
Figure 2: Performance degradation of AdaBoost and RMBoost methods increased levels of noise 'Credit' dataset.
robustness to label noise. The table also shows that the minimax risk optimized at learning is often near the RMBoost error in practice. Figure [ summarizes the trade-off between classification per- formance and robustness to noise for the 9 methods the datasets. Specifically, the vertical axis describes classification performance in terms of the average ranking in the noiseless case, while the horizontal axis describes robustness to noise in terms of the average difference between the error in noisy and noiseless cases. The figure shows that RMBoost is robust method that also provide a strong classification performance near that of AdaBoost method.
Figure ? further illustrates the classification performance and robustness to noise of RMBoost in comparison with AdaBoost. While Adaboost is able to achieve slightly better error with clean la- bels, its performance quickly deteriorates for increasing probabilities of noise, especially for adver- sarial noise. On the other hand, RMBoost provides strong classification accuracy on clean data that only mildly deteriorates with general types of label noise, in line with the performance guarantees presented.
7 Conclusion
The paper presents methods for robust minimax boosting (RMBoost) that minimize worst-case error probabilities and are robust label noise. Differently from existing techniques. we provide finite- sample performance guarantees that describe the effect of general types of label noise as well as the Bayes consistency of RMBoost methods. In addition, the paper presents and analyzes efficient algorithm for RMBoost learning, and experimenaally shows the effectiveness of RMBoost in prac- tice. The results in the paper show that the boosting methodology presented can enable achieve increased levels of robustness to label noise together with strong classification performance.
The column generation approach presented Section can be directly compared with other methods such LPBoost. However, as described above, the complexity of approaches based on column generation scales poorly with the number training samples, compared to other methods such AdaBoost LogitBoost (see also experimental running times in Appendix [H.)). The methodologies proposed can be implemented using alternative optimization approaches for large-scale optimization that may be more convenient computationally. The present paper focuses the new boosting methodology proposed and the theoretical analysis of its noise robustness. Hence, we leave for future work the development of more efficient learning algorithms.
Limitations:
A Acknowledgements
The authors would like to thank Prof. Yoav Freund for his comments and suggestions dur- ing the development of this work. Funding in direct support of this work has been provided by project PID2022-137063NBBBD funded by MCIN/AEI/10, 13039/501 10001 1033 and the Eu- ropean Union "NexxGenntrationEUUUPPRR
BCAM Severo Ochoa accreditation CEX2021-001 142- S/MICIN/AEI/IO, 13039/501 10001 1033 funded by the Ministry of Science and Innovation (Spain), and program BFRC-2022-2025 funded by the Basque Government. In addition, Verónica Álvarez holds a postdoctoral grant from the Basque Government.

---

References
[1] Leo Grinsztajn, Edouard Oyallon, and Gael Varoquaux. Why do tree-based models still out- perform deep learning on typical tabular data? In Advances in Neural Information Processing Systems, volume 35, pages 507-520, 2022.
[2] Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119 139, 1997.
[3] Jerome H. Friedman. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1 1as111899-2222 2001.
[4] Tianqi Chen and Carlos Guestrin. XGBoost: A scalable tree boosting system. In Proceed- ings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 784,794,220 2016.
[5] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. LightGBM: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, volume 30, pages 3 1146-3154, 2017.
[6] Robert E. Schapire and Yoav Freund. Boosting: Foundations and algorithms. MIT Press,
Cambridge, MA, 2012.
[7] Yoav Freund and Robert E. Schapire. Experiments with a new boosting algorithm. In Proceed- ings of the 13th International Conference International Conference Machine Learning, pages 148-156, 1996.
[8] Thomas G Dietterich. An experimental comparison of three methods for constructing ensem- bles of decision trees: Bagging, boosting, and randomization. Machine Learning, 40:139-157 2000.
[9] Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Additive logistic regression: statis- tical view of boosting. The Annals of Statistics, 28(2):337 407, 2000.
[10] Philip M. Long and Rocco A. Servedio. Random classification noise defeats all convex poten- tial boosters. Machine Learning, 78:287-304, 2010.
[11] Yoav Freund. An adaptive version of the boost by majority algorithm. In Proceedings of the 20th Annual Conference on Computational Learning Theory, pages 102-113, 1999.
[12] Yoav Freund. A more robust boosting algorithm. arXiv preprint arXiv:0905.2133 2009.
[13] Brendan van Rooyen, Aditya Menon, and Robert C Williamson. Learning with symmetric label noise: The importance of being unhinged. In Advances in Neural Information Processing Systems, volume 28, pages 10-18, 2015.
[14] Aritra Ghosh, Naresh Manwani, and P.S. Sastry. Making risk minimization tolerant to label noise. Neurocomputing, 160:93-107,2011
[15] Nontawat Charoenphakdee, Jongyeong Lee, and Masashi Sugiyama. On symmetric losses for learning from corrupted labels. In Proceedings of the 36th International Conference Machine Learning, pages 961-970, 2019.
[16) Philip M. Long and Rocco A. Servedio. The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss. Neural Computation, 34(6):1488-1499 May 2022.
[17] Naresh Manwani and P. S. Sastry. Noise tolerance under risk minimization. IEEE Transactions on Cybernetics, 133)):116-1155.1 2013.
[18] Jaeho Lee and Maxim Raginsky. Minimax statistical learning with Wasserstein distances. In Advances in Neural Information Processing Systems, volume 31, pages 2692-2701, 2018,
[19] Santiago Mazuelas, Mauricio Romero, and Peter Grünwald. Minimax risk classifiers with 0-1 loss. Journal of Machine Learning Research, 24(208):1-48, 2023.
[20] Santiago Mazuelas, Andrea Zanoni, and Aritz Pérez. Minimax classification with 0-1 loss and performance guarantees. In Advances in Neural Information Processing Systems, volume 33, pages 302-312, 2020.
[21] Soroosh Luufeezaadh-Abaadel Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103): 2019.

---

[22] Soroosh Shafieezadeh-Abadeeh Peyman Mohajerin Esfahani, and Daniel Kuhn. Distribution- ally robust logistic regression. Advances Neural Information Processing Systems, vol- ume 28, pages 1576-1584, 2015.
[23] Wei Gao and Zui-Hua Zhou. On the doubt about margin explanation of boosting. Artificial Intelligence, 203:1-18, 2013.
[24] Chunhua Shenand and Hanxi Li. Boosting through optimization of margin distributions. IEEE Transactions on Neural Networks, 21(():659 666, 2010.
[25] Ayhan Demiriz, Kristin Bennett, and John Shawe- Shawe-Taylor, Linear programming boosting via column generation. Machine Learning, (0(():225-2544 2002.
[26] Leo Breiman. Prediction games and arcing algorithms. Neural Computation, 11(7):1993-5117
1999.
[27] Lev Reyzin and Robert E. Schapire. How boosting the margin also boost classifier com- plexity. In Proceedings of the 23rd International Conference on Machine Learning, pages 753-760, 2006.
[28]
Akshay Balsubramani and Yoav Freund. Optimally combining classifiers using unlabeled data. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 211-225, 2015.
[29] Pascal Germain, Alexandre Lacasse, Francois Laviolette, Mario March, and Jean-Francis Roy. Risk bounds for the majority vote: From a PAC-Bayesian analysis to a learning algorithm. Journal of Machine Learning Research, 16(26):787-860, 2015.
[30] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learn- ing. MIT press, Cambridge, MA, second edition, 2018.
[31] Gábor Lugosi and Nicolas Vayatis. On the Bayes-risk consistency of regularized boosting methods. The Annals of Statistics, 32(1):30- 55, 2004.
[32] Peter L. Bartlett and Mikhail Traskin. Adaboost is consistent. Journal of Machine Learning Research, 8778)23347-2368, 2007.
[33] Dimitris Bertsimas and John N. Tsitsiklis. Introduction to linear optimization. Athena scien- tific, Belmont, MA, 1997.
[34] Chunhua Shen and Hanxi Li. On the dual formulation of boosting algorithms. IEEE Transac- lions on Pattern Analysis and Machine Intelligence, 32(12):221-2233 2010,
[35] Jean-Francis Roy. Mario Marchand, and François Laviolette. A column generation bound minimization approach with PAC-Bayesian generalization guarantees. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 1241-1249, 2016.
[36] Chunhua Shen, Hanxi Li, and Anton van den Hengel. Fully corrective boosting with arbitrary loss and regularization. Neural Networks, 48:44-58, 2013.
[37] Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, and Umar Syed. Structural maxent models. In Proceedings of the 32nd International Conference on Machine Learning, volume 33, pages 391-399, 2015.
[38] Jiaqi Luo, Yuedong Quan, and Shixin Xu. Robust-GBDT: leveraging robust loss for noisy and imbalanced classification with GBDT. Knowledge and Information Systems, pages 1-21, 2025.
[39] Jonathan M. Borwein and Qiji Zhu. Techniques of variational analysis. Springer, Berlin, 2004.
[40] Shai Shalay-Shwartz and Shai Ben-David Understanding machine learning: From theory to algorithms. Cambridge University press, New York, 2014.
[41] Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017.
12

---

Appendices
A
Strong duality lemma
Some of the proofs for the results in the paper make use of Fenchel duality for linear optimization problems over probability measures. The next lemma provides the strong duality result needed for such proofs.
Lemma 5.
Let U be uncertainty set given by (5) with À 0. For any T(X )), we have
max Pp ( (Ir, peu
1 -- (,;();)) A|ll|11 + HERT
= min
sup NEN,EE
{uh(x) p- (bh(y))))
(22)
Proof. In the first step of the proof, show that the right-hand-side in 22 is the Fenchel dual of the left-hand-side. Then, the result is obtained by showing that strong duality is satisfied for the uncertainty sets used in the paper.
Let M x )) be the set signed Borel measures over X x y with bounded total variation, and A be the linear mapping
A: M(X x)
R2T+1
(2 /a wh(x))dp(r,)) v) dp(z, v)
(23)
is bounded and its adjoint operator transforms 141 M2, E R27++1 to measurable functions over X' x V, A (11, M2, (2, v) yh(x) (M1 -22) +v.
Then, have
/ b(ylz))p(z,.) =1
max Ep 1o-1 (h, (z, v)) = max PEll
min f(p) ((A(p)) (24)
pell
PEM(XX))
where f and g are the lower semi-continuous convex functions
g 2T+1
R (oo)
0
if otherwise
a1 I a2 -
(25)
(a), b)
for r = 1 En Vita(r;), and
f M(X x y)
RU
[h(llr)dp(z,.) {
if otherwise.
p is nonnegative
(26)
Then, the Fenchel dual (see e.g., 39 of 24 is
sup
ff" M2. v)) (-(-1: -V)
(27)
where /' and 5² are the conjugate functions of f and g. If w is measurable function over V, we have
/ b((l:))))(()))))dpx(x))
(*(w) sup pzo
if oo otherwise
w(I,v) s b(y)z), Vr,y
and g²(( (-111 111
122 -V) is given by
sup s.t.
a 11
a 14 -
X1, a2 3 - + X1
(T A1)T 11 +(T (->1)) f2
if otherwise.
14 0, 112
0
13

---

Hence, the dual problem 27 becomes
inf
1 (T+ 14 (- (1) H2
s.t.
yh(x) (Jr - m2) + + V(r E x
11 - 0,-11 = 0
inf
1+ (T+ +111 p_ + ( M+ -+
s.t.
yh(x) (a(z))(pp)))) (1+ +1 h(yl)), (E, E xxxy
(28)
H4 = 0, =0
inf
μ 1- A||aa|l1 -V
14,2
(29)
S.t.
yh((x) T 1 + h(yla), V(r,y) E x {yh(x) 1 h(ylz)) |||/||
inf
1-T - T μ + sup
(30)
p
(x.))exx)
where we have taken p4, U2. μ = -1 and μ p4 m_ The equality in 29 is obtained
from (28) because in (28) we can consider only pairs 44 such that p + p = 1 p
because for any pair M4+ _l_ feasible in (28). we have j (u+ (M+- --4++ p__ (u p 14)+ is
feasible pair since f2+ ja_.. 14 ___, and we also have that Alii pi- A1 Aj -ii) S
A1 (u+ + p_). The expression in (30) is obtained since for any feasible (H, 1)) in (29) we have (j,, 17) is feasible if
D = inf (b(ylz) (
yh(x)) T1]
(xx))xxx
and i 2 V.
Then, we get that (30 is at least maXpeu Ep la-1 (h, (z, 9)}} by using weak duality, next we show that strong duality (and hence equality) is achieved. Specifically, in the following we show that strong duality holds because 0 E int(dom g Adom f) (see e.g., Chapter 4 in [39], where dom denotes the set where an extended-valuee function takes finite values, and int denotes the interior of a set.
We show that 0 < < A/ vT < 1, the ball B(O, e) with radius centered in 0 e R22+1 satisfies B(0,e) e) (dom g Adom f) 222+1
For any B(0,a) c 222++ there exist
E1 E B(0,A) A) C R such that
(2 (2)
z (T) Epp (vb(x)) (2)( + E1 - (2T+ {yh(x))
(2(T+1), x (T (2T) - Ep, (y)(()) + E2 + (1 2(2T-1) Bp. (ut((z)}
(2T+1)
(21+1))
for Pr ll the empirical distribution of the n training samples. Such equalities are obtained because we have
(1(x0) (() 2 (T)) - 2((T+1) Ep. (y]hx))/22 I s(1 + |Bp. (x)))(a))))) < A
(2T)) 2(2T+1 Ep.. {yk(x)} e(1 |Bp (yh())) <
since [b(x)] & 1 for any h E H.
Then, the result is obtained observing that EEp. (uh(x)) + E1, Ep. (wh(x)) + E2, 1) E domg
because Ep..yh(a) T. In addition, we have
(2-=((T+11)) EE, (2)((x)), 2(1+)()+)))BBB (yh())) (1 (1- (1-x())+1))) E A dom f
because |2(2T+ < < 1 and hence (1 2(2T+1)) Pn. is nonnegative measure.
Finally, since strong duality holds and 2f is not empty (p., E U)) we get that the optimal value in 22 is finite and hence the optimal in the dual is attained (39) and the 'inl" in (30) becomes 'min'.
14

---

B Auxiliary Lemmas
The next lemmas provide properties that are used multiple times in the proofs below.
Lemma 6.
-For any classification rule hy given by (8), we have
R(bp)) S 2 Ep- (p) p Epp (I(()) - _
5)
(31)
IIf p" is the distribution of training samples with label noise probabilities Pb for any function IR we have
Epr (uf(z)) = Ep- ( (x,,())))
(32)
Proof. The result in 31 is obtained because
11
yhx))) 1a + (Mx)) 1 2/2 5)) + y( h(x))( 1 1
(y(v) (+) 1
2.0
as a consequence of the definition of 11 in (8. Therefore, we have
) Yo K.y that directly leads to 31 since R(h,m = E. {1 h(ylz)}.
h (ylx)) 2 (x) P (I(() M -
(33)
The result in 32 is directly obtained because using get
[))((())) Ep; (1- pag
+ (1) - (-a) (+1lz)))
(us(()) - (x)()))
Lemma 7. Let Eest be given in (T0 and Pnoise be the probability with which label is incorrect at training. If is an Sogrsolution of (6), we have
R(hw)) s Tt Eape + (Eest 2Pnoise A)]lza|11-
(34)
Proof. Using (31 in Lemma aaooe, we get
R(hx) & F(1)) Bpp (h(x)) 141-11 1 ) (
< T2 Supt + Ep- y/((x)) - - Alll|l
after adding and subtracting A||m|/1 and T with t El 311(())). Therefore, the result is obtained by using Hölder's inequality because we have
(pp-y(())) -1oo0 S E (prry 1 a
Σ vr(((ss)
+ (p-y)(()) Rp Rp
(35)
Eest + 2Ep (1)())) Eest + 2P Pnoise
(36)
by using (32 in Lemma and the fact that [f(z)] < 1 vh H.
15

---

C Proof of Theorem 1
Using Lemma 5 in Appendix(Aland taking 1 n Ei=1 yil((z), we have
min max Bpp (4. (h, (r,,))) min heT(X,)) peu
1a + >llee|11 + sup
{ub(x)) 1 -- (--((yla)))
h.p
TEX.VEY
min - re + *lla||l + min sup (ub(L)) h(yl2)))
ZEN,
(37)
and
min sup (vb(z) P h(ylz)} --by))))) = min V h sEN.yEy
b,
s.t.
yd(()) h(ylz)) Sv, Vx E N,y E E..
In addition, we have
1
yh(x)) & h(ylz) S u4 Ve X,y sup max {1(x) T P 1-12 1, -x(x) μ 1, 2) 3Ex
since h1)la)) S and h11 |x) + h( ( 1 for any x E X, E y For each μa, we first prove that
there exists classification rule satisfying
1 -
h(ylz) 2 yh(x) sup max {h(x) μ - 1, -b(x) 1 - 1,
(38)
=EX
Clearly, we have
1 1
sup max (h(x) 12 1, 11-1,-((x) -(x))) 1 1, sE
2) 2
sup max (h(z) T -,xx))
yh(x) 1, E
Therefore, there exists a classification rule satisfying
38 because
Σ (y((x) μー - sup max (1(x) - 1, -hxx) 4 1, -11,--)) s Σ yh(x) /+ = 1, Va E x
sus zeX
2
vEY and
yEY
yh(2)) sup max (f(x)) 1- -(xx) 1 - s 11 E N.
=Ex
Then, such rules are solutions of
(uh(1) h(yl(())) sup max (Mxx) T - 1, -(xx) 1, 2
min sup >EX,EE>
xx
because for any h E T/), we have
sup (uh(z)] μ h(ylz)) sup ((ax)(((z)) h((1l))) -xxx) - 1a-hh-11pp b(-111)) xEX',EE
sex
sup max (hxx) T 4 - h(1l)) h(x)) h- 1(-111x),- -
se
sup max (hxx) 1 1, -xx)))) # 1, -
since
1 1 (bxz) 4 4- h1-((1)=)) 1
/ h(x)) 4 1a---hh-100 h(-1(z))
2 2
< max(f((x) T 14 h(1lz)) - M(x) T hi ((-1(=))
and if h satisfies
(8). we get
1
(yh(x)] 1 h(ylo)) < sup max (π(x) T 1 -h(x) 11 -
sup TEX.VEY
xEX
16

---

Therefore, we have that (37 becomes
min heT(X.)) pell
R (f (x, y))) min - - 1 >||
(39)
1
sup max (x()) 1.(r
1, -
2
and the result obtained by observing that if " is solution of (39. has satisfy
2 - h(x)
Ve N. n S 2'
Otherwise, we would have that
sup max (h(x) n² -1, -((x)) 1² -1, - 1 = sup max ((xx) 14-11-h((2 wEX
-((x) μ -1] 2 -1
=E
with C > 1. Then taking jú - p²/C /C the objective of (39 at such jú would become
te" +
{ sup max max(h(1) (h(x))
1
1
max
C h(x)
r: 2
C
xEX
+ > || + max
{a
sup max (h(x)) ,=, -b,-)(a) p²) 1 xEX
= -
C
= - - n² + Al| 111+ +1)
and hence the value i would be smaller than that μ² since C > and the optimum value in is positive, which is in contradiction with μ being a solution of (39). Then, hn- in 7 and F(u") are, respectively, a solution and the optimum value of (4) as a direct consequence of
39
R
D Proof of Theorem 2
Using 31 in Lemma 0 above, we have
R(ba) 2 Ep (vb(x)] 4} F(R) R + Copt
so that, using the definition of the minimax risk R and the function F(u) in
6 we get
R(hp) Eupt 1 Σ (da())) " 1 (yh(x) T #1 Allaa11
1 1 Σ mi(()))
T
Mo Al/oo
n
hence, adding and subtracting Ep- (n-(u)())) poo. we get
R(hp) S R(hn.) + Copt + y:N(a;;) Ep- (xb(x)) (n - pb) - \|la|| + All
since R(h,.)) = 1/2 Fp (uh(x)) p.) Therefore, the result in 1I obtained using the reverse
triangular inequality together with Hölder's is inequality and the fact that
1 Σ y.b(as)
(xp((((z))
1 Σ v.(())) + +1E (ub(x)) - (x((()))
x [xr((())))
Eest + 2 Possiee
using 32 in Lemma 6
For the second result, we have
1 Ep. (21(x)] (1) Ep. (16(x) ml -11 7
R(b,)) 2
17

---

using 31 in Lemma 0 Then, adding and subtracting (R - 102))/111111 - Pooosse)
we get
n
y:fi(ar))
R(h,) S Rp- (yb(x) 14) + Esp (1x(x) [4l 2
1
71
2l Pmisse
2fine noise
1=1
+
n
y: y:l((a)))) (1))
1
|
+
Epp
Epp
(1b(2) T p4
n1
moise
2 PPniise
moise
2P
P
moise
2P 2P noisee
(40)
using the definition of μ and oo and the fact that
Ep. [1(z)
π - 1/2
Eopt
F(U) + 1/2
2Phois
1 P
2 Proise
1 2Pooise
Grouping terms in (40) and using the fact that R(bm,))) = 1/2 - Epp (ut((x)) Not we get
Eopt
(-
y:h(z;) Ep- -ee--p--uuhpe (o-((()()))) (1e - 1o)
R(ha) < R(h,,)) +
Piniieee
2P Pnnise
1=1
+ 1 2P
(11 ||(111))
so that the result is obtained using the reverse triangular inequality together with Hölder's inequality and the bound
Eyp (yh(1)) Ep. (ub())) -||2 (p, P
Varp- (p) Pnoise
Pnoise
1
Pooie
that follows using
32 Proise
Bp- (po(z)). ( Jensen inequality, and the fact that [h(x)] < vh E H.
E
Proof of Theorem 3
Using
31 in Lemma
0 we have
1
R(ba) I Ep. (yh(x)) μ F(H) + R Eopt.
IfC = max(1, sup (2h(x) (gl)), the vector ug/ ls/C'n is feasible for (6, so that using the definition of the minimax risk R and the function F(U)) in (6 we get
n MB
R(ha) S Eopt
Σ
(l(l))) a Ep. [yb(x)) T μ All
((x)
alluall
n
n
C
Hence, adding and subtracting Ep- (x)) and Ep- {ut((T))] M4/ /C, we get
R(ba) R((haayes) + Eape +
y:1((ar) - EE- (ub()))))) (n C
MB - -Allell1
7
|1 + Ep. + C yyBBayos(2) (2)
y/((x)) T uB
(41)
2
C
18

---

since R(bbayes) = 1/2 Ep- (yybaays [2) For the last term in (41, we have
Ep
yh
yh(())
MB
Bayes (I)
h(x)
Mn
ydpp (z, v)
2
C
2
C
sup (B)yes((x) 2h(r) Pn
2 xEX
1
sup lIBaaes (1) 22((x) MBl
2 xex
2h(x) MB -2(xx) T MB
- sup
2 =EX
C
Sapprox
(2((x) MBl (1- 2
2
2 xEx
sup
E Eapprx
(C 1) S Eapprox
(42)
2
where 42 is obtained because C' or
C' = sup zEx
(2(x)
Mnl S sup (2h(r) ø
Pn h (x) + sup
|B (x) S Eapprox + 1.
xEX
For the third term in (4I) using Hölder's inequality we get
ubb(x;) - Ep- (vb(()))) T (u
My C
1 Ep- (ub(x))
vrh(z;)
MB
71
00
1 E (yh(1))
Σ n
vr
11
Mg
C
+ 1|pp {yh(x)}
Ep {ud(x))
MB
S(Eea + 2P Pooiss)
MB
Then, the result in (15) is obtained using the reverse triangular incquality and the fact that
Mn u
/o 11 < a Malli + (1 ) M|llll S || Malli + 1llll1
because C² 2
F Proof of Theorem 4
If (1]] < 1/2, have Ep; (1l/ (z), ha(2)),....,.
(1) 1/2)+ (k)
because
M(x) E [-1, for any h E H. Hence, (k) is éapé -optimll solution of (6) with Sopi = R(()) R.
(k)
so that the bound (20) is obtained as a direct consequence of the bound (34) in Theorem
For the case where (+)) 1 1/2, let F be the family of functions
F= (f(x) (x), h2(x), ... Nr, (I)) for some h1, I2,...,, E H. 111ll111 C}.
Using common properties of Rademacher complexity (see e.g., Chapter 26 in 40) we get that the Rademacher complexity of F is equal CR. Specifically, F is given by convex combinations of functions in H. scaled by C' because μ in the definition of F can be taken to be positive since we are considering sets of base-rules H. such that f H. whenever f E H. Hence, the family of functions
g = [g(x) (lf(=)) 1/2) for some f E F
has Rademacher complexity upper bounded by CR,, using Talagrand's contraction Lemma (see e.g., Chapter 26 in [40]) and the fact that function h(s) (Is) - 1/2), is 1- --pisschitz. In addition,
19

---

g(x) 10, (C - 1/2)+] for any 9 so that with probability at least 1 we have
Ep: (10)()), (2))), .... Mr (x)))(())
2 S n
(ax),, N2(s)),)))))......)) Mr, (vi))
2)
1
log(1/0)
+ 21 ll + (11xa(0)12
-/
2n
-2 log(1/5)
1
2 1 * l1 + (1110
=(6)
2n
(43)
using uniform concentration bounds based on Rademacher complexity (see e.g., Chapter 3 in (30]
Hence, μ (k) is an eop optiial solution of 06 with E Font (20
R(K) R + =()), so that the bound in in Lemma Zin Appendix
is obtained direct consequence of the bound 34
For the last result, Algorithm I stops round Step 5, we have
wiinh(x;) S. REH
Then, all the dual constraints are satisfied round it and we have that R( < R. Such inequality obtained because (k)) would be the optimal value of the primal in 16 using all the base-rules, and (I6) has the same objective and variables as (6) but with less constraints. Therefore, the result
is obtained because the suboptimality at round & satisfies s = R( R + s6) S e
G Effect in Algorithm 1 of the base learner suboptimality
The next result shows how the suboptimality of solutions found by Algorithm iss affected by possible early termination and the suboptimality of the base learner used in practice.
Theorem 8. If μ is solution of the optimization (16) using all the base-rules in H. Then, μ is (k) an Sop optimal solution of optimization (6) in Section for
(k) Eopt
max bEh
w.ihh(;;)) - >) ||||" + =(6)
(44)
with weights {w;} and labels {T:) } given by (19) using the dual solution round k.
Proof. We first show that
R(A) < R Ebuse |اا||1
(45)
for
w.ish((xs)) - )
Ebasc
max BER TL
Let or, 3 a dual solution of the optimization problem 16 solved at round By definition of weights {w; | and labels (Te / in (19), for any h H we have
Ebase > < [h(x)): 1((2). M(,, (a B y/n) < + Easee
In addition, the vectors n²= (1r ++ 1¹= = (-11²) )+ are feasible for the optimization problem
1 a
min
y (x+) (u+ - - + (A + Ebase ) (u+ + p_)
M _
71
1
s.t.
< hxx:)* (1+ - z. i = 1.2, 2.......
2
n. ł 0, 4_ 2 0.
(46)
20

---

where h is given by all the base-rules in H. Then, using weak duality we have
(*() = ] 1 - 1- 3)
1
-
2 (n(( (1 -1=" + (A + Chase) )1 (1 + p1
because a, a feasible solution of the dual of 446). Then, if iis the optimal value of (66 using all the base-rules in H. we have
R k)
R Ebase 1 (u² + p2)
so that the bound in 45 is obtained since R S R because Rt is the optimum value of an optimization problem with the same objective and variables as (6) but with less constraints. Therefore, the bound in 44 is obtained because
opi = (R(K) - R + e()) S Etusel |10 E())
The theorem above bounds the suboptimality of RMBoost rules determined at any round by Algo- rithm[]] The bound (44) accounts for the error due to the usage of relaxed constraints correspond- ing to the training samples through the term e(6). In addition, the first term in 444 accounts for the error due to a possible early termination as well as for the suboptimality in practice of the base learner used solve (88) Notice that such suboptimality of the base learner affects any boosting method [6] and is not a significant problem for Algorithm that only requires to find a violated constraint in the dual (not necessarily the most violated).
H
Implementation details and additional experimental results
In the following we provide further implementation details and describe the datasets used in Sec- tion Then, complement the results in the main paper by including the results obtained using multiple types of label noise, assessing the running times of the methods presented, and evaluat- ing the sensitivity to parameter X. In the first set of additional results, evaluate the classifica- tion performance of the proposed method in comparison with existing boosting methods in cases with uniform and symmetrie label noise well as adversarial noise; in the second set of addi- tional results, we further show the robustness to noise of RMBoost in comparison with AdaBoost; in the third set of additional results, we compare the running times of RMBoost with AdaBoost and LPBoost; in the fourth set of additional results, we further show the performance improve- ment of RMBoost using large datasets; and, in the fifth set set of additional results, we show that RMBoost has little sensitivity to the choice of hyperparameter A. In addition, the Github htttps://githin
womm/Machhneeeernnngggii wtw.e/aaraaaaaaaa/////ot---oo--e RMt//stBooot--oooo -erooosstNNeurrPe IPS- 2025 provides the code of the proposed RMBoost method with the setting used in the numerical results.
H.1 Implementation details and datasets utilized
We utilize 11 publicly available datasets that have been often use as benchmark for boosting meth- ods: Diabetes, German Numer, Credit, Blood transfusion, Titanic, Raisin, QSAR, Climate, Susy, Higgs, and Forest covertype. These datasets can found the UCI repository [41 and in www. kaggle.......................... com The main characteristics of the datasets used is provided in Table
The proposed RMBoost method is evaluated using multiple cases label noise: the conventional symmetric and uniform label noise (Vz, P+1(x) p-1(x) = Pooise) with P Pooise 10% and Phoise = 20%, and also an adversarial type of label noise with Pooise 10% and Proise 20%. This adversarial type of noise is implemented by flipping the labels of training instances that can be classified with high margin. Specifically, we flip the labels of the instances with the largest margins for a reference rule found with the LogitBoost method using clean labels. This type of label noise addressed by the theoretical results presented the paper and corresponds with non con-uniform and non-symmetric noise in which (x) = 1 if yh(x)) is large and (ソ((x) 0 otherwise, where h is the reference rule. Such type of noise describes practical situations in which an adversary chooses to change the labels in the examples that can result in the highest damage.
21

---

Table 2: Datasets characteristics
Dataset
Samples
Instances dimensionality
Diabetes
768
8
German Numer
1,000
24
Credit
690
15
Blood transfusion
748
4
Titanic
891
8
Raisin
900
7
QSAR
1,055
41
Climate
540
18
Susy
5,000,000
18
Higgs
11,000,000
21
Forest covertype
581,012
54
P.Poottt
I.Rrost
I.PRoost
Ronking without make
Robust-GBDT GBDDT XGB Quad
Kanking without sale
Robug--BBD GBDT
Robugt-GBIT GBDT
RobustBoost
XGB Quad
RobustBoost
XGB Quad
RobustBoost
BrownBoost
BrownBoost
Ronking without
BrownBoost
GentieBoost
GentleBosst
GentleBeost
LogitBoost
LogitBoost
LogitBoost
RMBoost
RMBoost
RMBoost
AdaBoost
AdalBoost
AdaBoost
>
noise error without noise [%6]
with noise omar without noise [%]]
with moose crror without [%]
(a) Unif. sym. case with Pauise 20%.
(b) Adversarial case with Pumise 10%.
(c) Adversarial case with Pavise 20%.
Figure 3: Trade-off classification performance vs robustness uniform and symmetric noise as well as adver- sarial noise.
The proposed RMBoost method is compared with 8 boosting methods: the state-of-the-ar tech- niques AdaBoost, LogitBoost, GentleBoost, and LPBoost together with the robust methods Ro- bustBoost, BrownBoost, XGBoost with quadratic potential XGGB-uuad) and Robust-GBDT, specif- ically designed for scenarios with noisy labels. RMBoost and all the methods used for comparison are implemented using default values for hyper-parameters and the code in standard libraries or provided by the authors. Methods RobustBoost, AdaBoost, LogitBoost, GentleBoost, and L.Boost are implemented using their Matlab codes, methods CGB--Qua and BrownBoost are implemented readthedocs. is and 'BrownBoost"
using the Python libraries 'XGBoost' htttps://ggboos /ttps: cww/ happllappsssaaaa 2ero0eeer000//00 www.://///oooooooooeooo respectively, and method Robust-GBDT is implemented using the code provided by the authors (38]. The proposed RMBoost implemented by learning parameters μ³" R and base-rules in /2,,... lt, using Algorithm [I and by predicting labels using the deterministic classifier hy, (x) = sign( [fi (z), (z) ., Fi [z)r)) In particu- lar, simplex-based solvers for linear optimization with tolerances for constraints and dual fcasibility 10-3, and we take À = 1/ in all the numerical results.
H.2 Additional experimental results
In the first set of additional experimental results, we further compare the classification eттоr of RMBoost with existing boosting methods. The results Table D in the paper as well as Table below are obtained carrying out 100 random and stratified train/test partitions with 10% test samples. Table in the paper shows the classification error obtained by the most representative methods with clean labels and with symmetric and uniform label noise with Pnoise = 10%. Table B shows the classification error obtained by the boosting methods with clean labels, with symmetric and uniform label noise with P Puoise 10% and Phoise 20%, as well as with adversarial noise with Punie 10% and Proise 20%. Over multiple datasets and types of label noise, Table together with Table 3 show that the minimax risks obtained at learning are often near the prediction ervor and that MBBoss can obtain top accuracies in comparison with existing boosting methods both in noise-less and noisy cases.
22

---

Table 3: Average classification error in % + st. dev. for RMBoost and state-of-the-art boosting methods.
Method
Titanic
German
Blood
Crodit
Diabetes
Raisin
QSAR
Climate
RohustBoost
2143.7
254-4.6
26-44,4
15+4,7
28+55.6
16+33.
16+33.5
9.1+22.9
AdaBoost
2043.2
244442
24=4.
1443.9
27:4.9
15+227
14=3.1
8.542.0
LPBoost
3245.7
28422
32=5.8
1624.3
2915.5
16:13.2
1613.1
8.342.0
Noise-less
LogitBoust
24145
27.4.33
1414..
2615.33
15:12.6
141:3.1
8.512.0
GentleBoost
22+-3.7
25444.6
26+-4.1
14+44.
27+55.2
15+-2.9
14+3.11
8.74-2.3
BrownBoost
20+3.7
2543.6
25-3.33
15+4.1
34+5.0
1543.9
14+3,4
11:24
Robust-GBDT
2343.9
2443.4
24=3.6
23444.8
3324,4
1643366
16#3.8
11:2.7
XGB-QU BGBBQuua
2113377
25.134
22:3399
22:15.6
3414..6
16.13.8
23.33.5
8.4:2.00
RMBoos
224:3.5
274-2.8
20-554
14-15.6
26+-4.5
124-3.6
15+3.1
7.54-2.00
Minimax risk
20+0.3
26++0.6
24:00.6
16+00.4
25
1440.66
17=0.5
9.34004
RobustBoost
294-3.99
26-44.2
314-5.3
204-3.9
19+44.0
AdaBoost
22+4.1
30+-4.2
27
18+4.55
31=5,2
19#3,9
19=3.5
12+2.8
Fisse = 10%
LPBoost
3516.1
3415.4
36=5.7
22:44.7
32-5.7
21:4.11
20=3.5
1243.6
LogitBuost
23.14.5
29.14.4
28.
19.14.5
29.15.1
19.14.1
1813.5
10.12.9
GentleBoost
24444.5
29444.2
29444,3
19+44.7
30+4.9
1944.0
18+-3.5
10429
BrownBoost
23.13.9
28.13.8
26.14.4
21:144
35.4,99
17.13.9
1813.8
11.12.8
Pobust-GBBTT
244-3.9
254-3.3
25+-3.2
26-45.66
34+44.1
20+4.11
19+-3.5
204-2.9
XGB-Quad
2243.9
274-4.1
23-3.4
2444888
34.44.5
20:3.4
26+44.7
10+3.2
RMBoost
22:3.6
2745.0
22=3.9
16:3.8
2715.11
14#2.4
20
9.542.8
Minimas
28.
28
23.00.8
RobustBoost
2414.0
3345511
28:4.88
25:5500
3425.6
25:14.9
25
20:1.99
AdaBeost
25.14.2
3..15.0
30.4.99
24.15.3
34.4.88
24.14.7
24.14.0
20.13.9
Pate 20%
L.Poost
3946.4
374-4.8
40-6600
28+-5.2
36+5,44
274-2.2
26+-4.3
17454
LogitBoost
28:4.44
33-2-.8
32=4.7
2446.0
32-5.3
23:24.6
24
14:442
GentleBoost
28:14.3
3415.2
32:4.8
25:5.2
3415.0
25:5.22
24
1424.2
BruwnBooo
28.14.8
31.1466
30.5.00
25.14.8
3815533
21.14.0
2314.44
15.14.1
Robust GBITT
314-433
194-3.6
KGB-Quad
23+4.6
29++4.2
24=3.7
26-66.1
35-5.00
20+4.11
26+
11+34
RMBoost
25:4.2
29::2.3
27=4.1
16:44.0
28:66.3
18:1.99
2423.3
20:13.7
Minimax risk
30:11.1
32.10.8
33:0.88
27.10.9
30
25.111
27100.6
20.11.1
Adversarial Fane = 20% Adversarial Pane 10%
RobustBoost
26:24.0
341-4.6
31:3,3
22:15.1
3715.88
23:14.2
23
17:14.6
AdaBoost
2643.99
3445500
32-4.9
22:4-88
36-6.2
23:3.88
24
1423.2
LPBoost
3815.7
38:14.6
40.5.88
25:15.5
38.55.6
24:14.4
2514.1
13:33.5
LogitBoust
2813..5
3...5.0
GentleBoost
28+-3.9
334-4.7
34+5511
22++4.6
35+-5.1
23+-3.7
22+-3.7
11+3.11
BrownBoost
2944.3
334-4.3
30=5.3
20+4.44
36-5.7
21+4.0
22+3.6
13+3.1
Robust-GBDT
28:3.8
3143399
28:4.11
23:44.7
3124.8
25:4.44
22:3.4
2416.2
XGB Quad
25.14.5
30.15.1
26.13.2
17.148
29144.7
19113.8
24.15.0
10.13.1
RMBons
254-5.4
274-3.9
26--3.1
194-5.1
22+-366
164-3.7
234-3.8
114222
Minimax risk
25+00.9
33++0.5
28-0.77
25+0077
29:0..5
21+1.
24
1740.5
RobustBoost
30+4466
444-5.6
36-5.77
33455
4645.66
3344.11
26+44.7
30+5.9
AdaBoost
30+4.2
43-15.3
37=5.7
32:55.4
46-6.0
33+4.33
27+4.3
30+5.2
LPBoost
42:15.7
46:1-.99
46:6.88
36:16.9
48:55.6
35:14.6
2514.8
42:15.6
LogitBorst
33:14.5
43.15.2
3915.99
32.1.566
45.55.8
33.14.1
22.14.5
33.1..2
GentleBoost
33-44.6
424-5.6
39-66.2
324-5.7
46--5.7
33444
22-44.7
33+6600
BrownBoost
3324.6
434-5.4
33-5.4
2945.00
46-5.7
31=4.00
22+4.8
33+5.2
Robust-GBDT
32:3.77
371-4.1
33:4.99
30:15.0
41:5.00
32:14.3
3815.0
3216.33
XGB Quad
29.5.00
3816.5
RMBonst
27455.4
314-3.4
34+5.88
20+-3.6
29+3.3
234-5.5
22+488
2745.5
Minimax risk
28-0.9
3540.3
33-0.9
2940.66
31-0.66
2741.6
1940.6
2840.7
Figure the paper as well Figure Jummmrrze the results in Tables aand terms of the trade-off between classification performance and robustness to noise. The vertical axis of the figures shows the classification performance in terms of the average ranking in the noise-less case, while the horizontal axis shows the robustness to noise in terms of the average difference between the error with noisy labels and that without noise. Figure and Table 4 extend the results in the main paper to uniform and symmetric label noise with P Puoise 20% and with adversarial noise with P Parise 10% and Paoise = 20% complementing those with uniform and symmetric label noise with Phoise 10% in Table and
and Figure ① Over multiple types of label noise, Figures [[ (3] together robust method that can also provide a strong classification performance near that of AdaBoost method.
with Table A show that RMBoost
In the second set of additional results, we further show the robustness noise of RMBoost in com- parison with AdaBoost. Figure 2 in the paper well as Figures 4a and Ab are obtained computing for each noise level the classification error over 500 random stratified partitions with 10% test sam- ples. Figures 4a and 4b extend the results using 'Diabetes' and 'Climate' datasets completing those similar behavior
the main paper that show the results using Credit dataset. to Figure 2 in the paper. In particular, the figures show that RMBoost method is significantly less
23

---

Table 4: Classification performance and robustness to noise for RMBoost and state cate-offfoee af-thh-art art boosting methods.
Ranking without noise
Error with noise error without noise [%]]
Method
Average rank
Noise 10%
Noise 20%
Adver. noise 10%
Adver. noise 20%
RobustBoost
5,94
3,08
7.37
7.30
15.22
AdaBoost
2.38
3,88
8.78
8.11
16.37
I.PBoost
6.94
4.39
8.97
8.01
18.12
LogitBoost
3.63
3.27
7.54
6.92
16.68
GenteBooost
4.69
3.38
7.88
7.19
16.16
BrownBoost
5.50
2.72
6.36
5.48
13,90
Robust-GBDT
6,63
2.82
3.75
5.75
13.26
XGB-Quad
6,00
1.65
2.83
3.53
RMBoost
3.31
1.71
4.10
3.88
10.82
50
AdaBoost uniform symmetric noise
AdaBoost uniform symmetric
AdaBoost adversarial noise
AdaBoost adversurial noise
RMBeost uniform and symmetric noise
30-
RMBoost uniform and symmetric noise
Clossification entor 1%6
RMBoost
Classifcation enon [98
adversarial
20
10
10
15
Noise probability P Pross 198
Noise probubility Paoee [%%]
(a) Diabetes dataset
(b) Climate dataset
Figure 4: Performance degradation AdaBoost and RMBoost methods increased levels noise.
affected by increased levels of noise. In particular, RMBoost performance only mildly deteriorates with label noise, accordance with the theoretical results shown in the paper.
H.3 Comparison in terms of running times
In the third set of additional results, compare the rumning times of RMBoost with those of AdaBoost and LPBoost. Figure 5 shows the relative running times the methods varying the training sizes using 'Credit' and 'QSAR' datasets (the absolute running times in all the methods the order of seconds in a regular desktop machine). The vertical axis in the figure represents the ratio between the learning running times for different training sizes divided by that achieved with 100 training samples averaged over 100 random partitions. In accordance with the discussion in Sec-
AdaBoost
AdaBoost
LPBoost
LPBoest
RMBoost
RMBoost
Relative running time
Relatie Relative ruaning time
Training size
Training size
(a) Credit dataset
(b) QSAR dataset
Figure 5: Comparison of relative running times vs training sizes for RMBoost, LPBoost, and AdaBoost.
24

---

Table 5: Average classification error in % + st. dev. for RMBoost and stale-of-the-art boosting methods.
Dataset
RobustB
AdaB
LPB
LogitB
GentleB
BrownB
GBDT
XGB-Q
RMB
Minimax
Noiseless
Susy
2421.7
2.4:1.8
3042.2
24=2.0
254:17
234177
25=1.8
2.21.6
23::2.0
23:0.3
Higgs
34+1.8
33+2.0
38+3.11
33-1,9
34+2.1
34+1.9
37=2.0
37+244
35+2211
33+0.3
Forestcov
2.=1.88
20++1.8
27+11.7
17=1.1
20+1.77
20+
26=2.0
33+1.7
22+:1.6
22+0.22
Susy
26+2.2
2.+-1.8
35+3.4
27-1.9
28+118
2.+
26-1.8
2.+-1.8
23+-1.9
28++0.4
10%
Higgs
3512.1
35:1.99
41:114
36=2.1
3742.3
35:22.2
39=2.2
3812.4
35::2.4
36:00.5
Forestcov
22:1..7
2.4:1.7
34119
22:1.2
25::..0
23:1.66
27=2.1
334:2.2
23::1.7
28:10.4
Susy
27+2.0
26++2.0
38+:2.2
30=2.1
32+2.00
25
29=1.6
25+
24+:2.0
32+0.5
20%
Higgs
37-2.3
37+2.00
46++3.3
38=2.3
3942.44
3742.33
41=2.9
39+2.7
364:2.2
39=0.66
Forestcov
2.
2.::1.88
3842.33
25.1.5
29::1.9
2.91199
32:2.1
34122.7
23::2.0
32:10.4
Adv 10%
Susy
3242.0
3242.1
431:2.7
34=2.0
3542.00
3143.3
3421.6
3312299
324:2.3
28:10.5
Higgs
39=2.0
3942.0
48+2.8
41=2.0
42+2.3
3843.4
44=1.
38
38#22.4
40=0..5
Forestcov
28
2842..0
40:22.2
28=2.1
29::2.3
28:22.0
27=1.7
28+22.3
28::2.1
31:0.5
Adv 20%
Susy
40=2.0
40:11.9
49+2..8
43=1.9
44#2222
40+1.5
41=2.3
39#2.0
38+22.5
33:0..5
Higgs
4911
50::2.2
4913.
49-2.7
49112.4
49:1..88
0.7
49:14.1
48.13.3
46:10.6
Forestcov
3942.5
3942.4
4743.8
38-2.2
40::2.2
39:2.11
38=1.4
3642.7
36::2.6
36200.7
Noiseless
Noiseless
Noiseless Noise 10%
Noise 10%
Noise 10%
Noise
Noise 20%
Noise
ciroe
Claviffication
Claciffiation
(a) German numer dataset
(b) Diabetes dataset
(c) Blood transfusion dataset
Figure 6: Performance of RMBoost method using multiple values of X.
tion of the main paper, the results depicted in the figure show that RMBoost can achieve similar running times LPBoost method, which also addresses linear optimization problem learning. As expected, AdaBoost method results in lower running times since does not require to solve an optimization problem at each round. Nevertheless, the complexity increase required by RMBoost is not significant and scales mildly with the training size.
H.4 Additional results with larger datasets
In the fourth set additional results, we further compare the classification error of RMBoost with existing boosting methods using large datasets. Table the paper and Table 3 in Appendix H.2 shows the classification error obtained by using small datasets (up to 1000 samples). The Table shows the classification error obtained by using 5,000 randomly drawn training samples from the 'Susy,' 'Higgs,' and 'Forest Covertype' datasets. Such table shows the results with clean labels, with symmetric and uniform label noise with Phoise 10% and Proise 20%, as well as with adversarial noise with Proise = 10% and Phoise = 20%. The additional results Table 5 show similar behavior those in and Juing small datasets. The proposed methods achieve adequate performance without noise together with improved robustness with noisy labels.
H.S Hyperparameter sensitivity
In the fifth set of additional results, we asses the sensitivity of the RMBoost method to the choice of hyperparameter A. These numerical results are obtained computing for each noise level the clas- sification error over 200 random stratified partitions with 10% test samples. Figure d shows the classification error in 3 datasets obtained by varying the hyperparameter X in cases without label noise and with 10% and 20% uniform and symmetric noise. The figure shows that the performance is not significantly affected by the choice of hyperparameter X. Although better results can be ob- tained by tuning the value of X, the default value of //v7 achieves adequate results in general.
25

---

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 claims in abstract and introduction accurately describe the paper contri- butions.
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 motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed over the paper. In particular the theorems state the hypothesis required.
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 "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 au- thors should reflect on how these assumptions might be violated 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
applicable, the authors should discuss possible limitations of their approach ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
26

---

Answer: [Yes]
Justification:
The detailed proofs appear in the appendices and the theorems state all the assumptions made.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data provided or not)?
Answer: [Yes]
Justification: The experimentation carried out in the paper is described in Section 5 and detailed in Appendix together with the details needed reproduce the results. In addition, the supplementary material provides Matlab and Python code that implement the methods presented in the experimental setting used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer 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.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture the contribution 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
fully might suffice,
specific model and empirical evaluation.
While NeurIPS does not require releasing code, the conference does require sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the partieular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in
27

---

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
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is provided in the supplementary materials and the data used is publicly available through the UCI repository [42] and in www.kaggle.com, as described in Appendix I.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please
the NeurIPS
and data submission guidelines http://bc/mmiiee///ttttttaaaaa/a
code
for more de-
tails.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results, See the NeurIPS code and data submission guidelines lnttps:/nnips.. http:////iiis.cppplbicc////eee/e httppuulic/guuueeeess
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 new proposed method and baselines. If 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 much information 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 chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: The experimental settings/details are described in Section 5, detailed in Ap- pendix I, and in the code provided in the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification: The experimental results provide error bars in terms of standard deviations over different random partitions of the data.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of 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
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The experimental results in the paper be carried out in regular desktop machine in few hours, as described in Appendix I.
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 as well as 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 t make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer:
[Yes]
Justification:
The research conducted conform with such Code of Ethies.
Guidelines:
The answer NA
that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in 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]
29

---

Justification:
The paper presents foundational research that is not tied to particular applica-
tions.
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 spe- cific 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 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 unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g.. pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper presents foundational research that is not tied to particular applica- tions/datasets.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to 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 is 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 paper refers to all the relevant previous works.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
30

---

The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, ppaerssithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the
cense 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 not 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 documenta- tion provided alongside the assets?
Answer: [Yss]
Justification:
The code provided is documented and easy to use.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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 is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
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 the main contri- bution 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, cura- tion, 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 the requirements of your country institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
31

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. 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 we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do 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 LLMSs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy for what should or should not be described.
32


Reviews:
[{"review_id": "0DKDTJRMZs", "reviewer": "Reviewer_L2j8", "summary": "The paper presents a novel method called Robust Minimax Boosting (RMBoost) that aims to enhance the robustness of boosting algorithms against label noise. The authors introduce a minimax approach that directly minimizes worst-case error probabilities and provides finite-sample performance guarantees. The paper also includes efficient algorithms for RMBoost learning and demonstrates through experiments that RMBoost not only withstands label noise but also achieves strong classification accuracy in practice.", "questions": "see my comments above.", "limitations": "no", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**  \n(1) The introduction of RMBoost, which focuses on minimizing worst-case error probabilities, is a novel advancement in the field of robust boosting methods.\n\n(2) The paper provides comprehensive theoretical guarantees, including finite-sample performance and Bayes consistency, which are well-supported by solid proofs.\n\n(3) Experiments are conducted to show that RMBoost outperforms existing methods in the presence of noisy labels and maintains high classification accuracy without noise.\n\n(4) The proposed learning algorithms are efficient and scalable, which can be applied to handle large datasets.\n\n**Weaknesses**   \n(1) While the experiments are thorough, additional testing on more diverse and real-world datasets (e.g., UCI ML datasets) could further validate the robustness and applicability of RMBoost.\n\n(2) The paper assumes certain types of label noise, and the robustness to other, less common types of noise does not seem to be fully explored. Other papers such as [1][2] from the reference list below, also discussed methods for handling other types of label noise, e.g., one-sided label noise. It would be great if the authors can discuss their differences and perhaps include them in the experiments if applicable. \n\n**Reference**:   \n[1] Liu, et al. \"An analysis of boosted linear classifiers on noisy data with applications to multiple-instance learning.\" 2017 IEEE International Conference on Data Mining (ICDM). IEEE, 2017.   \n[2] Luan, et al. \"Multi-Instance Learning with One Side Label Noise.\" ACM Transactions on Knowledge Discovery from Data 18.5 (2024): 1-24.", "was_revised": true, "final_justification": "Thanks for the authors' efforts on providing more results in the rebuttal. I remain my support to this paper :)", "rebuttal": "We thank the Reviewer for his/her careful reading of the paper and for the positive feedback and suggestions received. We believe we completely address below the comments from the Reviewer, and will be happy to answer any further question the Reviewer could have during the authors/reviewers discussion period.\n\n**Additional experimental results with more diverse datasets**\n\nThe experimental results in the paper show results using 8 publicly available real-world datasets commonly used to compare boosting methods. Five of them are available in UCI repository and the rest in Kaggle website. The instance dimensionality and label proportions in the datasets vary significantly among the datasets. Following the comment from the Reviewer, we have added additional results with other types of datasets that have a larger number of samples. The following table shows the additional results obtained using 5,000 samples from the datasets Susy, Higgs, and Forestcov that can be found in UCI repository.\n\n|           | Dataset   | RobustB  | AdaB     | LPB      | LogitB   | GentleB  | BrownB   | GBDT     | XGB$-$Q    | RMB      | Minimax  |\n|-----------|-----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n|           | Susy      | 24±1.7 | 24±1.8 | 30±2.2 | 24±2.0 | 25±1.7 | 23±1.7 | 25±1.8 | 24±1.6 | 23±2.0 | 23±0.3 |\n| Noiseless | Higgs     | 34±1.8 | 33±2.0 | 38±3.1 | 33±1.9 | 34±2.1 | 34±1.9 | 37±2.0 | 37±2.4 | 35±2.1 | 33±0.3 |\n|           | Forestcov | 20±1.8 | 20±1.8 | 27±1.7 | 17±1.1 | 20±1.7 | 20±1.5 | 26±2.0 | 33±1.7 | 22±1.6 | 22±0.2 |\n| | | | | | | | | | | | |\n|           | Susy      | 26±2.2 | 24±1.8 | 35±3.4 | 27±1.9 | 28±1.8 | 24±1.8 | 26±1.8 | 24±1.8 | 23±1.9 | 28±0.4 |\n| $P_{\\text{noise}} = 10%$     | Higgs     | 35±2.1 | 35±1.9 | 41±1.4 | 36±2.1 | 37±2.3 | 35±2.2 | 39±2.2 | 38±2.4 | 35±2.4 | 36±0.5 |\n|           | Forestcov | 22±1.7 | 22±1.7 | 34±1.9 | 22±1.2 | 25±2.0 | 23±1.6 | 27±2.1 | 33±2.2 | 23±1.7 | 28±0.4 |\n| | | | | | | | | | | | |\n|           | Susy      | 27±2.0 | 26±2.0 | 38±2.2 | 30±2.1 | 32±2.0 | 25±1.9 | 29±1.6 | 25±1.7 | 24±2.0 | 32±0.5 |\n|  $P_{\\text{noise}} = 20%$       | Higgs     | 37±2.3 | 37±2.0 | 46±3.3 | 38±2.3 | 39±2.4 | 37±2.3 | 41±2.9 | 39±2.7 | 36±2.2 | 39±0.6 |\n|           | Forestcov | 24±1.8 | 24±1.8 | 38±2.3 | 25±1.5 | 29±1.9 | 25±1.9 | 32±2.1 | 34±2.7 | 23±2.0 | 32±0.4 |\n| | | | | | | | | | | | |\n|           | Susy      | 32±2.0 | 32±2.1 | 43±2.7 | 34±2.0 | 35±2.0 | 31±3.3 | 34±1.6 | 33±2.9 | 32±2.3 | 28±0.5 |\n| Adversarial  $P_{\\text{noise}} = 10%$   | Higgs     | 39±2.0 | 39±2.0 | 48±2.8 | 41±2.0 | 42±2.3 | 38±3.4 | 44±1.2 | 38±1.7 | 38±2.4 | 40±0.5 |\n|           | Forestcov | 28±1.9 | 28±2.0 | 40±2.2 | 28±2.1 | 29±2.3 | 28±2.0 | 27±1.7 | 28±2.3 | 28±2.1 | 31±0.5 |\n| | | | | | | | | | | | |\n|           | Susy      | 40±2.0 | 40±1.9 | 49±2.8 | 43±1.9 | 44±2.2 | 40±1.5 | 41±2.3 | 39±2.0 | 38±2.5 | 33±0.5 |\n|  Adversarial $P_{\\text{noise}} = 20%$       | Higgs     | 49±2.1 | 50±2.2 | 49±3.4 | 49±2.7 | 49±2.4 | 49±2.8 | 49±0.7 | 49±4.1 | 48±3.3 | 46±0.6 |\n|           | Forestcov | 39±2.5 | 39±2.4 | 47±3.8 | 38±2.2 | 40±2.2 | 39±2.1 | 38±1.4 | 36±2.7 | 36±2.6 | 36±0.7 |\n\nThe table above with additional results shows similar behavior as that in the experimental results of the submitted manuscript. The proposed methods achieve adequate performance without noise together with improved robustness with noisy labels.\n\n**Generality of the label noise considered in the paper and one-sided label noise**\n\nWe would like to emphasize that the label noise considered in the paper is totally general (lines 78-79), and includes the one-sided label noise in [1] [2]. Specifically, any label noise is described by a function $\\rho_y(x)$ that quantifies the probability with which the label of an instance $x$ is flipped from $y$ to $-y$. In the case of one-side label noise, the function $\\rho_y(x)$ satisfies that $\\rho_{+1}(x)=0$ and $0\\leq\\rho_{-1}(x)\\leq1$ for all $x$, for cases where only the negative samples are affected by noise; respectively, $0\\leq\\rho_{+1}(x)\\leq1$ and $\\rho_{-1}(x)=0$ for all $x$, for cases where only the positive samples are affected by noise. The results in the paper consider arbitrary functions $\\rho_y(x)$ so that they are valid for any type of label noise. We thank the Reviewer for pointing out the type of noise “one-sided label noise” that will be described in the final version of the paper updating the lines 78-86 with the corresponding references.\n\nWe agree with the Reviewer that incorporating one-sided label noise into the experimental results can further validate the methods proposed. So that we have carried out other additional results in which we use one-sided noise, both uniform and adversarial (only one class affected by noise). The following table shows these additional results with one-sided label noise, in experimental results as those shown in Figure 2 of the submitted manuscript.\n\n\n|          |          | Method | 3%       | 6%       | 9%       | 12%       | 15%      | 18%       | 21%      | 24%      | 27%      | 30%      |\n|----------|----------|--------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n| Uniform|    Diabetes       | AdaB   | 27±4.5 | 27±5.5 | 29±5.2 | 30±5.2 | 31±5.2 | 32±5.6 | 33±5.4 | 34±5.2 | 35±5.5 | 38±5.6 |\n| noise | | RMB    | 26±4.8 | 26±5.0 | 27±4.8 | 27±5.3 | 27±4.4 | 29±4.9 | 29±5.4 | 30±5.7 | 32±5.6 | 35±5.3 | \n| | | | | | | | | | | | |\n| Adversarial |    Diabetes       | AdaB   | 32±5.8 | 34±4.7 | 34±4.5 | 35±4.7 | 37±4.2 | 44±4.3 | 45±4.3 | 46±4.2 | 47±4.2 | 48±4.2 |\n| noise | | RMB    | 26±4.5 | 26±5.7 | 27±4.9 | 32±6.5 | 35±4.0 | 36±4.7 | 36±5.6 | 38±5.2 | 40±4.3 | 43±4.8 |\n| | | | | | | | | | | | |\n| Uniform|  Raisin          | AdaB   | 15±3.5 | 16±3.7 | 16±3.7 | 17±4.1 | 19±3.9 | 20±3.8 | 20±4.3 | 22±4.5 | 23±4.2 | 25±3.7 |\n| noise |          | RMB    | 15±3.4 | 15±3.6 | 15±4.0 | 15±3.9 | 15±3.6 | 16±2.4 | 17±4.1 | 17±4.0 | 18±4.3 | 19±4.5 |\n| | | | | | | | | | | | |\n| Adversarial |    Raisin       | AdaB   | 17±3.5 | 18±3.7 | 21± 3.9 | 22±3.7 | 24±3.7 | 24±3.5 | 26±3.9 | 31±4.1 | 31±3.9 | 31±3.7 |\n| noise | | RMB    | 14±3.9 | 17±2.7 | 17±2.6 | 18±3.9 | 19±3.4 | 19±2.7 | 20±5.0 | 23±4.7 | 24±3.7 | 27±4.8 |\n\nThe results above shows that the proposed techniques are also robust to one-side label noise."}, {"review_id": "SI6sqk7vTc", "reviewer": "Reviewer_TwM6", "summary": "The paper presents a novel boosting framework designed to improve robustness against general types of label noise, called Robust Minimax Boosting (RMBoost). Existing boosting methods provide theoretical robustness guarantees for symmetric and uniform/non-uniform label noise, but they only offer bounds in expectation, not for finite samples. Moreover, the accuracy of these methods often drops significantly. RMBoost, instead, aims to be robust while also maintaining high accuracy. It directly minimizes the worst-case error probabilities over an uncertainty set defined by the training samples and base rules—that is, the base models of the boosting algorithm, where empirical averages can deviate from expected values within a threshold. The paper proposes an alternative formalization of the problem, whose solution is a classifier formed by a linear combination of the base rules. Moreover, the resulting classifier is proven to be optimal for minimizing the worst-case error, and the paper provides and proves a bound on its maximum error in the presence of label noise. The paper also proposes an efficient column generation algorithm for learning RMBoost rules. The experimental evaluation considers four state-of-the-art training techniques, four robust training techniques, and eight relatively small tabular datasets suited for training boosted models, evaluating both symmetric and uniform label noise as well as adversarial label noise. The experiments demonstrate RMBoost’s higher resilience to label noise and its comparable performance to standard boosting algorithms in the absence of noise.", "questions": "- Why was this baseline [A] not included in the experimental evaluation? Can you add it?\n- Could you explain why larger and more realistic datasets such as Covtype, HIGGS, or SUSY were not included and if you plan to evaluate you approach on them?\n\n**Update after rebuttal**\nThe authors have clarified the omission of baseline [A] in the experimental evaluation, explaining that they attempted to include this baseline but its performance did not reach the same level as the one of the other baselines in the paper. Regarding the second question, the authors provided results on a limited portion of the suggested datasets, that support the effectiveness of their approach. They have also clearly stated the limitation of their method in handling large tabular datasets. I find this more than acceptable, given that the limitation is explicitly acknowledged in the paper.", "limitations": "The paper should include a limitations section clearly stating the proposal's limitations, such as the additional computational time required compared to other training solutions like AdaBoost and the absence of evaluation on large datasets.\n\n**Update after rebuttal**\nThe authors will add this section in the final version of their work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Thanks to the authors for submitting this interesting paper. I appreciate the effort to provide theoretically well-grounded algorithms for training machine learning classifiers—particularly boosted models, that are both accurate and robust to noise (random or adversarial), as I believe such properties are highly desirable in practical applications. I think this is a good paper that proposes a solid theoretical contribution, although I believe the experimental evaluation could be improved a bit. I detail below the strengths and weaknesses of the paper and hope that the authors can address my questions during the rebuttal phase.\n\n\n## Strengths\n\nRegarding novelty, this paper is certainly original, as it concerns the problem of finding boosted models that are robust to general label noise (not just specific types of noise), characterizing their robustness as a function of the noise, and ensuring they remain accurate. The theoretical contributions are well-grounded (all proofs are provided in the Appendix) and appreciable, since they demonstrate the existence of a boosted model that minimizes the worst-case error and for which it is possible to theoretically characterize both robustness to general noise and accuracy. Finally, the experimental evaluation is adequate, although it could be improved; it considers several baselines and datasets and shows that the proposed model is more robust and sufficiently accurate compared with previous works.\n\n## Weaknesses\n\nFirst, the experimental evaluation considers both uniform-symmetric and adversarial label noise. However, in Section 2.2, the paper mentions [A], which provides robustness results going beyond symmetric and uniform cases, including cases with symmetric non-uniform noise. This baseline is not considered in the experimental evaluation, even though integrating it would be very interesting since RMBoost is designed to handle general label noise. I suggest that the authors include this baseline or specifically explain why it was not considered.\n\nSecond, I suggest considering more realistic and larger datasets in the experimental evaluation, such as Covtype, HIGGS, and SUSY from the UCI Machine Learning Repository, which have also been previously used to evaluate tree ensembles (e.g., in [B]). This addition would make the experimental evaluation more convincing. If it is not possible to include these datasets, I kindly ask the authors to explain why.\n\n## Minor\n- line 107, page 3 -> should it be $\\phi$ and not $\\phi'$?\n- line 156, page 4 -> \"margins' distribution\" -> \"distribution of the margins\"\n- line 210, page 5 -> \"base-rules' values\" -> \"values of the base rules\"\n\n[A] Ghosh et. al., Making risk minimization tolerant to label noise, Neurocomputing, 2015.\n\n[B] Chen et. al., Robustness Verification of Tree-based Models, in NeurIPS 2019.", "was_revised": true, "final_justification": "I recommend the acceptance of this work. This paper is original, since it addresses the problem of finding boosted models that are robust to general label noise and not just specific types, while characterizing their robustness as a function of the noise and ensuring they remain accurate. The theoretical contributions are well-grounded (all proofs are provided in the Appendix) and they demonstrate the existence of a boosted model that minimizes the worst-case error and for which it is possible to theoretically characterize both robustness to general noise and accuracy. The experimental evaluation is adequate; it considers several baselines and datasets, and shows that the proposed model is more robust and sufficiently accurate compared to models proposed previously in the literature. Both the experimental evaluation and the clarity of the proposal have been improved during the rebuttal, where the authors provided additional experimental results supporting the robustness of their models against noise.", "rebuttal": "We thank the Reviewer for his/her appreciation of the theoretically well-grounded algorithms and the solid theoretical contribution. We also thank the Reviewer for the suggestions and comments provided that are addressed below. We will be happy to answer any further question the Reviewer could have during the authors/reviewers discussion period.\n\n**Experimental comparison with the methods analyzed in reference [14]**\n\nAs described by the Reviewer, the results in reference [14] show robustness results that go beyond the common symmetric and uniform noise. Specifically, such work shows that certain potential functions (e.g., sigmoid) are also robust to symmetric and non-uniform label noise (in cases where the Bayes risk is zero). The submitted paper describes the results in [14] as one of the few works that go beyond the symmetric and uniform noise. However, the methods described in [14] are not directly comparable experimentally with the methods proposed: the results in [14] are not oriented to boosting methods and the potential functions analyzed are non-convex. Specifically, the classification rules considered in [14] are linear rules and quadratic-kernel rules, not ensembles of base-rules. In addition, the reference [14] utilizes dedicated optimization algorithms to deal with the non-convexity of the potential function, which have an unclear generalization in boosting settings. Nevertheless, over the past few days, we have used the XGBoost library to implement boosting methods with the potential functions proposed in [14]. This library allows the use of customized potential/loss functions. However, the performance obtained was significantly worse than that of all the other methods. We guess this is due to the non-convexity of the potential functions in [14].\n\n**Additional experimental results with larger datasets**\n\nThe specific learning algorithm proposed in Section 5 of the paper to solve the minimax problem (4) is based on column generation approach for linear optimization, similarly as other methods such as LPBoost. A known limitation of approaches based on column generation is that their complexity increases with the number of samples faster than other boosting methods such as AdaBoost (see discussion on lines 279-306 and running times in Figure 5 comparing AdaBoost, LPBoost, and the proposed RMBoost). Notice also that approaches based on column generation have not been implemented in the reference [B]. For instance, the size of the optimization problems solved by the column generation methods increases linearly with the number of samples. Therefore, the usage of such approaches with large scale datasets with millions of samples require specialized optimization methods such as parallel solvers, dual decompositions or core-set selection, which go beyond the scope of the submitted paper.  In the final version of the paper, we will extend the description of this topic in the paragraph about computational complexity in relation with the reference, and state this limitation in the new section for limitations.\n\nNevertheless, we agree with the Reviewer that it is of interest to include additional experiments with larger datasets than those used in the submitted manuscript (up to 1k samples). Hence, we have carried out new experimental results with the datasets suggested by the Reviewer, where the limitations of the column generation methods have been addressed by using a subset of the datasets composed by 5,000 samples. The following table shows the results obtained for different types of noise.\n\n|           | Dataset   | RobustB  | AdaB     | LPB      | LogitB   | GentleB  | BrownB   | GBDT     | XGB$-$Q    | RMB      | Minimax  |\n|-----------|-----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n|           | Susy      | 24±1.7 | 24±1.8 | 30±2.2 | 24±2.0 | 25±1.7 | 23±1.7 | 25±1.8 | 24±1.6 | 23±2.0 | 23±0.3 |\n| Noiseless | Higgs     | 34±1.8 | 33±2.0 | 38±3.1 | 33±1.9 | 34±2.1 | 34±1.9 | 37±2.0 | 37±2.4 | 35±2.1 | 33±0.3 |\n|           | Forestcov | 20±1.8 | 20±1.8 | 27±1.7 | 17±1.1 | 20±1.7 | 20±1.5 | 26±2.0 | 33±1.7 | 22±1.6 | 22±0.2 |\n| | | | | | | | | | | | |\n|           | Susy      | 26±2.2 | 24±1.8 | 35±3.4 | 27±1.9 | 28±1.8 | 24±1.8 | 26±1.8 | 24±1.8 | 23±1.9 | 28±0.4 |\n| $P_{\\text{noise}} = 10%$     | Higgs     | 35±2.1 | 35±1.9 | 41±1.4 | 36±2.1 | 37±2.3 | 35±2.2 | 39±2.2 | 38±2.4 | 35±2.4 | 36±0.5 |\n|           | Forestcov | 22±1.7 | 22±1.7 | 34±1.9 | 22±1.2 | 25±2.0 | 23±1.6 | 27±2.1 | 33±2.2 | 23±1.7 | 28±0.4 |\n| | | | | | | | | | | | |\n|           | Susy      | 27±2.0 | 26±2.0 | 38±2.2 | 30±2.1 | 32±2.0 | 25±1.9 | 29±1.6 | 25±1.7 | 24±2.0 | 32±0.5 |\n|  $P_{\\text{noise}} = 20%$       | Higgs     | 37±2.3 | 37±2.0 | 46±3.3 | 38±2.3 | 39±2.4 | 37±2.3 | 41±2.9 | 39±2.7 | 36±2.2 | 39±0.6 |\n|           | Forestcov | 24±1.8 | 24±1.8 | 38±2.3 | 25±1.5 | 29±1.9 | 25±1.9 | 32±2.1 | 34±2.7 | 23±2.0 | 32±0.4 |\n| | | | | | | | | | | | |\n|           | Susy      | 32±2.0 | 32±2.1 | 43±2.7 | 34±2.0 | 35±2.0 | 31±3.3 | 34±1.6 | 33±2.9 | 32±2.3 | 28±0.5 |\n| Adversarial  $P_{\\text{noise}} = 10%$   | Higgs     | 39±2.0 | 39±2.0 | 48±2.8 | 41±2.0 | 42±2.3 | 38±3.4 | 44±1.2 | 38±1.7 | 38±2.4 | 40±0.5 |\n|           | Forestcov | 28±1.9 | 28±2.0 | 40±2.2 | 28±2.1 | 29±2.3 | 28±2.0 | 27±1.7 | 28±2.3 | 28±2.1 | 31±0.5 |\n| | | | | | | | | | | | |\n|           | Susy      | 40±2.0 | 40±1.9 | 49±2.8 | 43±1.9 | 44±2.2 | 40±1.5 | 41±2.3 | 39±2.0 | 38±2.5 | 33±0.5 |\n|  Adversarial $P_{\\text{noise}} = 20%$       | Higgs     | 49±2.1 | 50±2.2 | 49±3.4 | 49±2.7 | 49±2.4 | 49±2.8 | 49±0.7 | 49±4.1 | 48±3.3 | 46±0.6 |\n|           | Forestcov | 39±2.5 | 39±2.4 | 47±3.8 | 38±2.2 | 40±2.2 | 39±2.1 | 38±1.4 | 36±2.7 | 36±2.6 | 36±0.7 |\n\n\nThe additional results show similar behavior as that in the experimental results of the submitted manuscript. The proposed methods achieve adequate performance without noise together with improved robustness with noisy labels.\n\n[B] Chen et. al., Robustness Verification of Tree-based Models, in NeurIPS 2019.\n\n**Specific section dedicated to the limitations of the methods proposed**\n\nWe thank the Reviewer for the suggestion provided about a section dedicated to the methods’ limitations in terms of training complexity. In the submitted manuscript, the limitations are described on lines 279-306 and lines 658-668. As suggested by the Reviewer, the new section for limitations will state the additional computational time required by the column generation method in comparison with other existing approaches, and the related limitation in the usage of datasets with millions of samples (the final version of the paper will include the new experimental results shown above).\n\n**Minor comments**\n\nWe thank the Reviewer for pointing few typos and suggestions to improve the writing that will be addressed in the final version of the paper. Regarding the usage of $\\phi$ or $\\phi'$ in line 107, the correct usage is $\\phi'(0)<0$ since the condition required for a potential function is that the derivative at zero is negative, that is, the potential function should be decreasing at zero since positive margins should be preferred to negative margins (see condition 2 in Definition 1 of reference [10])."}, {"review_id": "oABcteXKi6", "reviewer": "Reviewer_5GJn", "summary": "This paper formulates a min-max optimization method over uncertainty sets (max), finding a sequence of base learners minimizing the loss. This seems analogous to DRO, though the authors only give brief mention to this. The authors present several analytical results, and a convincing set of empirical results over many baseline models and datasets.", "questions": "1. Could you please reformulate both Eq 5 and 7 s.t. I can understand the intuition of these problems? \n\n2. Could you also present Algorithm 1 in more abstraction, so that someone might understand it outside of the dense notation?", "limitations": "The authors don't address this issue. The authors state \"The limitations are discussed over the paper. In particular the theorems state\n697 the hypothesis required.\" but this misses the above intent and makes finding relevant text 'throughout' very difficult. Presumably, the authors state about the scope of their problem: if the assumptions or hypotheses don't hold then their method might fail (i.e. every method's most general limitation).", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Overall, the authors present a rigorous set of analytical results on a novel model. (Presumably) the proofs seem to be of high quality and require a good deal of analysis in the appendix lemmas.\n\n2. The method seems to evaluate quite well. The authors primary results demonstrate consistent quantitative results (Table 1), and some simple qualitative and runtime results (in Appendix). So, the method does seem to have strong, practical value. \n\nWeaknesses:\n\n1. Overall, this was an extremely difficult paper to interpret. While I am familiar with both ERM and DRO works, I found the presentation to be very difficult to translate to those works. The notation is very terse, and the authors don't elaborate on base-rules, or the uncertainty set in (5). While I understand this refers to a \"uncertainty set,\" I don't actually understand the intuition of (5): 140-144 define the terms but don't give a high level statement outside of notation. \n\nSince this is a primary element in the minmax formulation (defined after the problem formulation in (4)), I have to reduce my confidence to 1, and adjust the quality and clarity. I further could not interpret the Thm 1 or its proof (including its lemmas) \n\n2. Similar to 1, even the algorithm description is impenetrable to me. This is primarily a wall of symbols with insufficient description. One could scarcely implement this method from this algorithm box.  The authors only cite one subproblem (16). Further use of this might mitigate the presentation complexity. Overall, from Algorithm 1 I couldn't describe the method in any more technical terms than Eq (4). \n\n3. The authors could improve their related work to better taxonomize the gap they are addressing. The authors mix some of the \"background\" notation, which takes away from the presentation of the gap. This really muddles the primary contributions (which are presented in L44, but are less specific in the prior work)", "was_revised": true, "final_justification": "The authors present significant analytical results for the proposed minimax boosting procedure.", "rebuttal": "We thank the Reviewer for the suggestions provided regarding notations and more intuitive descriptions. We trust the explanations provided below can help the Reviewer to get a more clear interpretation of the results presented and the relation with the related work. In case there are still some notational barriers limiting the results clarity, we would appreciate if the Reviewer let us know what specific notations are unclear so that we could further elaborate in the updated manuscript. \n\n**Notation clarification and intuition for uncertainty sets and Theorem 1**\n\nWe plan to use the extra page allowed in the final version of the paper to further clarify the notation used with a more intuitive description. Regarding base-rules, the theoretical sections of the paper consider general families of base-rules (any family of bounded functions from $\\mathcal{X}$ to $[-1,1]$). In some parts of the main text as lines 246-248, 321-324, and in the experimental results, the family of base-rules is given by decision trees, which are the common type of base-rules used in boosting methods.\n\nThe uncertainty set in (5) is composed by all the probability distributions over instance-label pairs for which expectations of the base-rules are near their empirical averages over the training samples. Specifically, the expectations used to define the uncertainty set are correlations between labels and base-rules predictions ($y \\boldsymbol{\\hbar}(x)$). The rationale for the usage of such uncertainty set is to have a small set that can contain the true underlying distribution of samples with high probability. The uncertainty set in (5) is small because the family of base rules is often very large so that (5) is given by a large number of constraints. The uncertainty set in (5) contains the true underlying distribution with high probability because base-rules are simple functions for which uniform convergence of sample averages is ensured.\n\nTheorem 1 shows that the minimax problem in (4) is equivalent to a tractable convex optimization problem (linear optimization with L1-regularization). This result enables to address (4) in practice by solving the tractable problem (6). The main idea behind the proof of Theorem 1 is substituting the inner maximization in (4) by its Fenchel dual, so that the minimax problem becomes a convex optimization problem.\n\n**More intuitive formulation of Equations (5) and (7)**\n\nRegarding equation (5) for the uncertainty set, other way to formulate the same uncertainty set is as follows. Let $\\mathcal{H} =\\lbrace h_1, h_2, \\dots, h_T \\rbrace $ be the set of all base-rules, e.g., all the decision trees with a bounded number of nodes given by components of the instances in the training set. The uncertainty set in (4) is\n$$\\mathcal{U}=\\lbrace\\text{prob. dist. }\\mathrm{p}\\text{ over }\\mathcal{X}\\times \\mathcal{Y}\\text{ such that }|\\mathbb{E}_p\\lbrace y h_j(x)\\rbrace -\\frac{1}{n} \\sum\\_{i=1}^n y_i h_j(x_i)|\\leq \\lambda,\\text{ for all }j=1,2,…T\\rbrace$$ that is, $\\mathcal{U}$ is given by the $2T$ linear constraints  $$\\frac{1}{n}\\sum\\_{i=1}^n y_i h_j(x_i)-\\lambda\\leq \\sum\\_{x,y} p(x,y) yh_j(x)\\leq \\frac{1}{n}\\sum\\_{i=1}^n y_i h_j(x_i)+\\lambda,\\  \\mbox{ for } j=1,2,\\ldots,T$$\nThe Lagrange (Fenchel) multipliers of such constraints correspond to the parameters $\\boldsymbol{\\mu}$ in Theorem 1.\n\nRegarding equation (7) for the minimax classification rule, other way to formulate the equation defining the classification rule is as follows. Let $\\boldsymbol{\\mu}^{\\*}=[{\\mu}^{\\*}\\_1, {\\mu}^{\\*}\\_2,…, {\\mu}^{\\*}\\_T]^{\\dagger}$ be the solution of optimization problem (7).\n\nA solution of the minimax problem in (4) is given by\n$$h\\_{\\boldsymbol{\\mu}^{\\*}}(y|x)=y \\sum\\_{j=1}^T h_j(x){\\mu}^{\\*}\\_j +1/2$$\nthat is, the minimax classification rule is given by a linear combination of the base-rules $\\mathcal{H}=\\lbrace h_1,h_2,…, h_T\\rbrace$ with coefficients given by a solution of the optimization problem (6). For instances $x$ for which the combination of base-rules $\\sum\\_{j=1}^T h\\_j(x)\\mu^{\\*}\\_j$ is positive, the probability $h_{\\boldsymbol{\\mu}^{\\*}}(y=+1|x) $ is larger than 1/2 and hence larger than $h_{\\boldsymbol{\\mu}^{\\*}}(y=-1|x)$, so that the deterministic classifier predicts label +1, (otherwise the classifier predicts label -1). Therefore, the determinist minimax classifier is given by\n$$h_{\\boldsymbol{\\mu}^{\\*}}(x)=\\text{sign}(\\sum\\_{j=1}^T h_j(x)\\mu^{\\*}_j)$$\nas shown in equation (8).\n\n**Abstract description of Algorithm 1**\n\nAlgorithm 1 follows a similar approach to other boosting methods based on column generation [25,34-36]. In each boosting round, a base learner finds the new base-rule (e.g., decision tree) by finding a base-rule that best fits a set of weighted samples ${(x_i,\\tilde{y}_i,w_i)}$ obtained from the training samples (line 3 of the Algorithm). Then, the coefficients for the current set of selected base-rules are obtained by solving the linear optimization problem (16) (line 7 of the Algorithm) and the dual solution of such optimization is used to obtain the weighted samples ${(x_i,\\tilde{y}_i,w_i)}$ for the next boosting round (lines 12 and 13 of the Algorithm).\n\n**Specific section dedicated to the limitations of the methods proposed**\n\nIn the submitted manuscript, the limitations of the methods proposed in terms of training complexity are described on lines 279-306 and lines 658-668. The new section dedicated limitations will state the additional computational time required by the column generation method in comparison with other existing approaches, and the related limitation in the usage of datasets with millions of samples."}, {"review_id": "ZgdSYQcoQT", "reviewer": "Reviewer_YmwY", "summary": "The paper introduces RMBoost, a boosting method that directly minimizes the worst-case error probability over an uncertainty set of distributions. This provides a principled approach to achieving robustness against label noise, moving beyond the use of specific surrogate loss functions. The key contributions are: (1) A novel minimax formulation for robust boosting that is shown to be equivalent to a tractable convex optimization problem. (2) Finite-sample performance guarantees that, unlike much prior work, holds for general types of label noise and explicitly characterizes the impact of noise properties.", "questions": "1. The minimax risk R computed by the algorithm is shown to be a good estimate of the final classification error (Table 1). Could this value be used in a practical way, for example, for model selection? For instance, could one use R to help tune the hyperparameter λ without a separate validation set?\n\n2. The margin constraints in the optimization problem (6), prevent any single data point from having an arbitrarily large positive or negative margin, which intuitively explains the robustness. How does this compare to other regularization techniques in boosting, such as explicitly penalizing the variance of the margins as in [23, 24]?", "limitations": "nothing to add", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nPrincipled and Novel Formulation: The core contribution—framing robust boosting as a distributionally robust optimization problem (Eq. 4-5)—is elegant and powerful. It sidesteps the often heuristic choice of robust potential functions (e.g., unhinged, sigmoid) and instead tackles the problem from first principles by directly minimizing the worst-case 0-1 loss. Showing this is equivalent to a tractable linear program (Theorem 1) makes the approach practical.\n\nStrong and General Theoretical Guarantees: The paper provides significant theoretical results. The finite-sample generalization bound (Theorem 2) is a key strength. It holds for general label noise, going beyond the common but restrictive assumptions of symmetric or uniform noise. The bound's explicit dependence on the noise probability (Pnoise) and variance (Varp∗{ρy(x)}) offers a much clearer picture of how different noise characteristics affect performance. Furthermore, the proof of Bayes consistency (Theorem 3) establishes the method's soundness in the limit of expressive base-learners.\n\nEfficient and Scalable Algorithm: The proposed learning algorithm (Algorithm 1), based on column generation, is a standard and well-suited technique for this type of problem (similar to LPBoost). This demonstrates that the theoretically-principled formulation does not come at the cost of practicality. The analysis of the algorithm's convergence and optimality (Theorem 4) is also a valuable contribution.\nWeaknesses\n\nThe weaknesses of this paper are minor and do not detract from the overall quality of the work.\n\nMotivation for Hyperparameter Choice (λ): The performance of the method depends on the radius of the uncertainty set, λ. The authors propose a default value of λ=1/\\sqrt(n), which is well-motivated by standard concentration inequalities. While the sensitivity analysis in Appendix H (Figure 6) is excellent and shows that the method is not overly sensitive to this choice, the main text could benefit from a slightly deeper discussion. For instance, briefly mentioning that this parameter could be tuned via cross-validation and explaining the trade-off it controls (a larger λ implies more robustness but potentially more bias) would be helpful for the reader.\n\nClarity on the Adversarial Noise Model: The adversarial noise model is a good way to test a worst-case scenario. However, its definition relies on a \"reference rule found with the LogitBoost method using clean labels\" (Appendix H, line 611). This implies an oracle with access to the true labels is needed to construct the noisy dataset for the simulation. This is perfectly acceptable for an experimental setup, but it should be stated with perfect clarity in the main text that this is a simulated worst-case attack designed to probe the algorithm's limits, rather than a naturally occurring noise process, to prevent any misunderstanding.", "was_revised": true, "final_justification": "I thank the authors for their replies to my questions. I maintain my support of this work.", "rebuttal": "We would like to thank the Reviewer for his/her appreciation of the principled approach proposed to achieve robustness against label noise. We also thank the Reviewer for the suggestions and comments provided that are addressed below. We will be happy to answer any further question the Reviewer could have during the authors/reviewers discussion period.\n\n**Extended discussion for the hyper-parameter $\\lambda$**\n\nFollowing the Reviewer’s suggestion, we plan to use the extra page allowed in the final version to expand the discussion about the hyper-parameter $\\lambda$, as follows. The hyper-parameter $\\lambda>0$ accounts for the error in the finite-sample average in (5) and can be selected using standard cross-validation approaches. This selection can be enhanced taking into account the family of base-rules used or prior knowledge on the amount of label noise. In particular, more complex families of base-rules or increased levels of noise can benefit from higher values for $\\lambda$. A simple default value for such parameter is $\\lambda=1/\\sqrt{n}$, which is the value used in all the experimental results in the paper (Appendix H further analyzes the sensitivity of the proposed methods to the choice of that hyperparameter). Overall, the hyperparameter $\\lambda$ controls the method’s robustness to underlying distributions that depart from the empirical distribution of training samples. In particular, larger values for $\\lambda$ can result in increased robustness (larger uncertainty set) but too large values for $\\lambda$ can result in minimax rules that are too conservative since the uncertainty set would contain quite adversarial distributions.\n\n**Rationale for the adversarial noise model used in the experimental results**\n\nAs described by the Reviewer, the type of adversarial noise model used in the experimental results does not occur naturally in cases where the noise has a stochastic origin. Such type of noise can be thought of as an extreme case used in the experimental results to test the robustness potential of the methods proposed. In addition, such type of noise can be thought of as a type of label corruption that could be injected in a dataset by an adversary. Specifically, an adversary could have access to a clean dataset and modify the labels that the adversary considers could harm the most the learning algorithm. We will clarify this rationale for the adversarial noise used in the experimental results, to avoid possible confusion. \n\n**Usage of the minimax risk $R$ for model selection**\n\nThis is a very interesting question from the Reviewer. Indeed, we believe that using that value for model selection can be quite appropriate, and somehow similar to the approach proposed in [37] to select the family of base-rule considered using performance bounds. Specifically, the hyper-parameters of the trees used (e.g., maximum number of terminal nodes, maximal depth, and minimum number of leaf samples) or the number of boosting rounds could be selected using the minimax risk $R$ without requiring a separate validation set. However, the value of the minimax risk $R$ is not very adequate to select the hyper-parameter $\\lambda$ since, for any dataset, larger values for $\\lambda$ will result in larger values for the minimax risk $R$, as the uncertainty set in (5) increases with $\\lambda$. \n\n**Relation between the margin constraints in optimization problem (6) and variance penalization in other methods**\n\nBoth ideas are algorithmically quite different but are somehow related in the sense that both approaches can achieve an increased distribution of margins. An average margin near its maximum value (1/2) together with the margin constraints in (6) force all the margins to be high (near 1/2). Similarly, a large average margin together with a small margin variance would also result in increased distribution of margins. However, the optimization problem resulting in cases with variance penalization is quite different to that in (6). In particular, the maximization of the average margin coupled with a minimization of the margins’ variance is a multiobjective problem that is addressed in existing works by using a hyperparameter that balances the relevance of both objectives. In addition, the subsequent optimization problem is quadratic due to the variance term and, to the best of our knowledge, there are no theoretical results describing the robustness to label noise of methods based on variance penalization."}]

Author rebuttal:

Meta-review: This work develops a boosting method, directly minimizing worst-case error probabilities, that is tolerant to label noise. They provide an efficient implementation and exhibit experimentally that their algorithm performs well in practice. After some discussion, the reviewers agreed that this work is above the acceptance threshold, hence I recommend acceptance.
Decision: Accept (poster)