acceptodds
Withdrawn from ICLR 2027

Minimax Boosting with Strong Rules

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Current boosting methods excel at combining weak rules, such as decision trees, that are well-suited to certain types of tabular data. However, they cannot effectively combine strong rules, such as neural networks, which are required for data with a hierarchical structure. Existing boosting approaches generalize poorly with strong rules because they greedily minimize empirical losses disregarding out-of-sample expected losses. This paper presents MBoost, a minimax approach for boosting that can effectively leverage strong rules. Unlike existing methods, MBoost minimizes worst-case expected losses and accounts for the generalization behavior of base rules. Both theoretical and experimental results show that MBoost methods can achieve excellent performance with strong base rules, overcoming the limitations of current approaches.

Primary area:
learning theory
Keywords:
Boosting, strong rules, distributionally robust learning, minimax learning, neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_G93BOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces MBoost, a minimax boosting method meant for strong base rules like neural networks. The key idea is an uncertainty set where each rule's expected error can differ from its training error by at most λk\lambda_k. Through duality, the minimax problem becomes a convex objective (Eq. 8). In this objective, each rule gets an L1L_1 penalty equal to its own estimated generalization gap. Theorem 2 bounds the risk using these estimates, and Theorem 3 relates it to the Bayes risk. The algorithm estimates λk\lambda_k on a fresh held-out split in each round. The authors test it on 9 image datasets with ResNet-50, 9 tabular datasets with fitcauto, and a synthetic index-2 task.

Critical strengths

1. Per-rule penalty derived from duality. The core idea is good. For neural networks, a Rademacher penalty over a whole subfamily (as in DeepBoost) is too loose and treats all networks alike. A penalty based on each rule's own held-out gap is more practical, and here it follows directly from the duality rather than being a heuristic. I checked the proofs in Appendices A–D and did not find errors.

2. Calibration. The method also calibrates well. Because the log-loss is strictly proper, the learned rule equals the worst-case conditional distribution. The ECE results in Table 1 and Figs. 3 and 5 are consistent with this.

Critical weaknesses

In short, I find the theory clean, but I could not confirm that the experiments test the proposed method. There are two kinds of gaps.

Gaps between the theory and the algorithm. These are not errors in the proofs. Theorem 2 gives an upper bound only when λ≥λ∗\lambda \ge \lambda^{\ast}. The algorithm uses a point estimate, which will be below λ∗\lambda^{\ast} about half the time. The analysis also uses the true marginal px∗p_x^{\ast}, while Algorithm 1 uses the empirical one. I would like the authors to discuss both, and perhaps try λk\lambda_k plus a confidence width.

Gaps between the algorithm and the released code. MBoost.py does not run as provided. Line 119 is indented by 9 spaces, so Python raises an IndentationError, and train_files (line 159) is never defined. I therefore cannot tell if this script produced Table 1. Please treat the points below as questions. If they hold for the real experiments, they affect the main results.

  1. Frozen backbone. In round 1, freeze_backbone=True makes every ResNet layer non-trainable (lines 38, 96–97). Later rounds reuse that model as it is (line 43). Only the 2-unit head is ever trained. The paper, however, says the pretrained weights are fine-tuned (lines 1050–1051). Were the image base rules only linear heads on fixed features? Were the baselines set up the same way?

  2. Coefficients applied incorrectly. Both scripts fit the solver on Z=ℏ/λZ = \hbar/\lambda, so the fitted coefficients equal λkμk\lambda_k\mu_k. Predictions and sample weights then use these coefficients directly (py lines 144, 149; m lines 42, 46). In effect, each rule is weighted up by λk\lambda_k. Rules that overfit more therefore count more, which goes against the purpose of the method. The fitted intercept is also discarded in both scripts. In the Python version, the weight formula on line 144 has the wrong sign: it gives hμ(y∣x)h^\mu(y|x) and not 1−hμ(y∣x)1-h^\mu(y|x) as in Alg. 1. The MATLAB version gets this right. Also, liblinear with C=1C=1 shrinks the effective penalty to λk/n\lambda_k/n.

  3. Held-out leakage. The data is reshuffled in every round (Alg. 1, line 8), but image models start from the previous round's weights (lines 1054–1055). The current held-out points were likely seen in training before. This should make λk\lambda_k too small. Tabular models are retrained from scratch, so they are fine. A fixed held-out set, or results without warm starts, would settle this.

  4. Estimating λk\lambda_k. With only 100 held-out points, λk=0\lambda_k = 0 can happen. That leads to division by zero and violates the interior condition of Lemma 4. How do the authors handle it? On Heart, Haberman and Ion, each fitcauto call gets only about 173–216 points. An ablation on nheldn_{\text{held}} would be useful.

  5. Experimental setup. MBoost.m gives fitcauto 30 seconds per round (line 4), but the paper reports 360 seconds. It also uses one 10% holdout, not 10-fold CV. On tabular data, Table 4 shows MBoost running about 15 times longer than the baseline. This conflicts with the claim of no extra overhead (line 447), so a baseline with equal compute is needed. The image ensemble only re-initializes the final layer, which makes it a weak comparison. Finally, several bolded wins in Table 1 lie within one standard deviation. Paired tests over the folds would help.

Questions for authors

Clarification requests (could change my assessment):

  1. Was Table 1 produced with the released scripts, or with different code? MBoost.py does not run as provided (indentation error at line 119; train_files undefined at line 159).
  2. Were the image base rules only linear heads on a frozen ResNet-50 backbone, as freeze_backbone=True in round 1 implies? Were the baselines set up the same way?
  3. Is the fitted coefficient vector rescaled by 1/λk1/\lambda_k before it is used for predictions and sample weights, and is the intercept intentionally discarded? Is the sign of the weight formula in MBoost.py (line 144) a bug?
  4. How is λk=0\lambda_k = 0 handled, given the division by λk\lambda_k and the interior condition of Lemma 4?
  5. Which setting was used for the tabular experiments: fitcauto with 30 s per round and a single 10% holdout (as in MBoost.m), or 360 s and 10-fold CV (as in the paper)?

Suggested additional experiments:

  1. Image results with a fine-tuned backbone and a fixed held-out set (or without warm starts).
  2. A compute-matched baseline on tabular data.
  3. An ablation on nheldn_{\text{held}}, and a variant using λk\lambda_k plus a confidence width.
  4. Paired significance tests over the folds for Table 1.

I am willing to raise my score if the authors (i) confirm or fix the code behind Table 1, (ii) report results with a fine-tuned backbone and a fixed held-out set, and (iii) include a compute-matched baseline.

Reviewer_RgbvOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a boosting strategy that allows the use of strong base learners while avoiding overfitting. The paper analyzes this problem theoretically and experimentally shows that MBoost avoids overfitting and improved model calibration by using a held-out set of examples during the boosting process.

Critical strengths

The study of how to ensure that strong learners can be combined effectively without overfitting using boosting is interesting.

The theoretical analysis of the problem leads to concrete improvements in the implementation of boosting with strong base learners when compared to AdaBoost with strong base learners.

Critical weaknesses

The paper lacks motivation: why is boosting for strong learners useful? What is the goal? Do you want stronger performing models? This could be stated much more explicitly.

The experiments do not convincingly show that boosting is preferred over using single strong learner models: a boosted model has much more trainable parameters than a single base model. For the tabular datasets, the paper does not show how traditional tree-based boosting models perform.

Given the recent successes of tabular foundation models, it would be interesting to at least mention where this method is positioned with respect to tabular foundation models for tabular datasets.

Minor comments:

  • line 024: "boosting methods are widely regarded as the preferred approach for tabular data [...] (see e.g., Grinsztajn et al. 2022)" This is outdated, see 1. However, this does not invalidate the research question in this paper.
  • line 034: "[...] since their empirical losses are no longer dependable proxies of actual expected losses." and line 037 "[...], with some rules closely matching expected and empirical losses and others exhibiting substantial overfitting." I'd expect a references to papers supporting these points.
  • Line 128: "[...], the generalization gap is lower than 1.36/(n)1.36/\sqrt(n) with probability at least 0.95 [...]." I'd expect a reference here back this claim up.
Questions for authors
  • What I am missing in the intro is a motivation for why you would want to apply boosting to strong base learners. As indicated in the paper, boosting was originally formalized to combine weak learners to make a combined stronger learner. In the model complexity (number of parameters) versus performance tradeoff, is it ever beneficial to boost strong learners?
  • The introduction claims that stronger base learners are necessary for data with hierarchical structures. Are the dataset in the evaluation examples of such datasets? Could you show that traditional tree-based learners fail on these (tabular) datasets, showing the need for a strong base learner?
  • Line 066: You indicate that strong rules are well-suited for ensembles and cite two papers Laksminarayanan et al. 2017 and Nam et al. 2021. You indicate that diversity between ensemble members is important. Could you clarify why, in the context of this paper, diversity is important? Is the goal of this paper the same as the two cited papers? The first paper uses ensembles to improve uncertainty estimation as an alternative to Bayesian NNs. The second paper tries to get rid of ensembles by distilling them into a single model. If the purpose of this paper is to improve uncertainty estimation (as the citation of Lakshminarayanan et al., 2017 suggest), is boosting a promising approach to improve the member diversity that is required to improve uncertainty estimates?
  • Line 133: "[...] for distributions with most of their mass far away from the training instances, the generalization gaps are large." What assumptions do you make on the training samples? Are they iid from p∗p^*? How likely is this case then?
  • What is the relationship of this approach and minimax approaches used for learning robust models? E.g. 2 for NNs.
Reviewer_gGqLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MBoost, a minimax boosting method using strong base learners such as neural networks. The method estimates individual generalization gaps and incorporates them as weighted L1 penalties in a convex optimization framework. TThe authors establish theoretical risk bounds and demonstrated promising performance on both tabular and image datasets, with computational costs comparable to those of other ensemble methods.

Critical strengths
  1. The paper provides a minimax formulation with theoretical guarantees connecting generalization gaps to regularization to mitigate the issue of overfitting for strong learners in the boosting framework.
  2. The empirical results are promising, showing improvements in classification accuracy and calibration with competitive computational costs.
Critical weaknesses
  1. Learning rate is essential to overcoming overfitting in boosting method, but the author didn’t discuss the effect of the learning rate in comparisons for Adaboost. Since smaller learning rates can mitigate overfitting, it remains uncertain whether MBoost offers substantial advantages over sufficiently tuned conventional boosting.
  2. The reliability of generalization-gap estimation requires further justification. Algorithm 1 reuses samples across boosting rounds, and neural networks are initialized from previous rounds. Consequently, held-out samples may have already influenced the fitted models. Moreover, reserving samples for validation reduces the effective training size, which may be problematic for small datasets.
Questions for authors
  1. How does sample reuse across boosting rounds affect the reliability of the generalization-gap estimates, especially when neural networks are initialized from previous rounds?
  2. Why are standard gradient-boosted tree baselines such as XGBoost missing in tabular datasets?
  3. How sensitive is MBoost's performance to the held-out sample size, particularly for small datasets?
  4. Can the proposed minimax boosting framework be extended to regression problems with continuous outcomes?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.