Research map / Learning theory and algorithms / Prediction and decision losses
Robust Minimax Boosting with Performance Guarantees
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes robust minimax boosting (RMBoost), which minimizes worst-case error probability over distributions constrained to match base-rule training averages, reduces to an LP solved by column generation, and gives finite-sample robustness and Bayes-consistency guarantees.
Problem
Boosting is highly sensitive to label noise; existing robust boosting methods lack finite-sample guarantees for realistic (asymmetric, adversarial) noise, lack Bayes-risk guarantees, and often have poor noiseless accuracy.
Approach
Learn classification rules by minimax risk minimization over an uncertainty set of distributions defined by base-rule expectations (rather than KL or Wasserstein balls), which reduces to a convex LP with L1 regularization; this avoids choosing a surrogate potential and yields margin-bounded, noise-robust rules.
Key results
- On 8 datasets with 10% symmetric/uniform label noise, RMBoost achieves the lowest error on Blood (22%), Credit (16%), Raisin (14%) and Climat (9.5%) among compared methods in the noisy setting, per the table.
- In noiseless settings RMBoost is competitive with AdaBoost (e.g., 14% vs 14% on Credit, 12% vs 15% on Raisin, 7.5% vs 8.5% on Climat), per the table.
- Finite-sample bounds show error of RMBoost scales with noise via 1-2P_noise and estimation error decays as O(sqrt(log n / n)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RMBoost instead of AdaBoost | Boosting on Raisin · Raisin (no noise) | classification error (%): 15±2.7 -> 12±3.6 | Helped |
| Use RMBoost instead of AdaBoost | Boosting on Raisin · Raisin (10% uniform symmetric noise) | classification error (%): 19±3.9 -> 14±2.4 | Helped |
| Use RMBoost instead of AdaBoost | Boosting on Credit · Credit (10% uniform symmetric noise) | classification error (%): 18±4.5 -> 16±3.8 | Helped |
| Use RMBoost instead of AdaBoost | Boosting on QSAR · QSAR (no noise) | classification error (%): 14±3.1 -> 15±3.1 | Hurt |
| Use RMBoost instead of LogitBoost | Boosting on QSAR · QSAR (10% uniform symmetric noise) | classification error (%): 18±3.5 -> 20±3.3 | Hurt |
| Use RMBoost instead of AdaBoost | Boosting on Titanic · Titanic (10% uniform symmetric noise) | classification error (%): 22±4.1 -> 22±3.6 | No clear effect |
| Use RMBoost instead of AdaBoost | Boosting on Blood · Blood (no noise) | classification error (%): 24±4.4 -> 20±5.4 | Helped |
Surprising findings
- Existing robust methods such as quadratic-potential boosting can have unsatisfactory accuracy even without noise, which RMBoost aims to avoid.
Limitations
- Column generation complexity scales poorly with the number of training samples compared with AdaBoost or LogitBoost.
- Bayes consistency requires base-rules that can approximate the Bayes rule (epsilon_approx = 0).
- Hyperparameter lambda must be chosen (default 1/sqrt(n)), with effects on performance depending on noise and base-rule family.
Experimental setup
Datasets: Titanic German Blood Credit Diabet Raisin QSAR Climat
Benchmarks: Titanic German Blood Credit Diabet Raisin QSAR Climat
Metrics: classification error (%)
Baselines: AdaBoost LogitBoost GentleBoost LPBoost RobustBoost BrownBoost XGBoost (quadratic potential) Robust-GBDT
Builds on: AdaBoost LPBoost RobustBoost BrownBoost XGBoost
Closest papers by meaning
- The Many Faces of Optimal Weak-to-Strong Learning (NeurIPS 2024 · similarity 0.87)
- Revisiting Agnostic Boosting (NeurIPS 2025 · similarity 0.85)
- Improving Neural Network Generalization on Data-Limited Regression with Doubly-Robust Boosting (AAAI 2024 · similarity 0.85)
- Sample-Optimal Agnostic Boosting with Unlabeled Data (ICML 2025 · similarity 0.85)
- Label Noise: Ignorance Is Bliss (NeurIPS 2024 · similarity 0.85)
- $\epsilon$-Softmax: Approximating One-Hot Vectors for Mitigating Label Noise (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.