Improved Replicable Boosting with Majority-of-Majorities

Kasper Green Larsen, Markus Engelund Mathiasen, Clement Svendsen
Proceedings of The 37th International Conference on Algorithmic Learning Theory, PMLR 313:1-18, 2026.

Abstract

We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. First, we create an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. (2022). We then use this algorithm with a constant accuracy parameter and run another layer of boosting on top to achieve the desired accuracy. This outer layer of boosting is inspired by the classical AdaBoost algorithm while capping the weights for a smoother distribution over the data which we show ensures replicability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v313-larsen26b, title = {Improved Replicable Boosting with Majority-of-Majorities}, author = {Larsen, Kasper Green and Mathiasen, Markus Engelund and Svendsen, Clement}, booktitle = {Proceedings of The 37th International Conference on Algorithmic Learning Theory}, pages = {1--18}, year = {2026}, editor = {Telgarsky, Matus and Ullman, Jonathan}, volume = {313}, series = {Proceedings of Machine Learning Research}, month = {23--26 Feb}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v313/main/assets/larsen26b/larsen26b.pdf}, url = {https://proceedings.mlr.press/v313/larsen26b.html}, abstract = {We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. First, we create an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. (2022). We then use this algorithm with a constant accuracy parameter and run another layer of boosting on top to achieve the desired accuracy. This outer layer of boosting is inspired by the classical AdaBoost algorithm while capping the weights for a smoother distribution over the data which we show ensures replicability.} }
Endnote
%0 Conference Paper %T Improved Replicable Boosting with Majority-of-Majorities %A Kasper Green Larsen %A Markus Engelund Mathiasen %A Clement Svendsen %B Proceedings of The 37th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Matus Telgarsky %E Jonathan Ullman %F pmlr-v313-larsen26b %I PMLR %P 1--18 %U https://proceedings.mlr.press/v313/larsen26b.html %V 313 %X We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. First, we create an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. (2022). We then use this algorithm with a constant accuracy parameter and run another layer of boosting on top to achieve the desired accuracy. This outer layer of boosting is inspired by the classical AdaBoost algorithm while capping the weights for a smoother distribution over the data which we show ensures replicability.
APA
Larsen, K.G., Mathiasen, M.E. & Svendsen, C.. (2026). Improved Replicable Boosting with Majority-of-Majorities. Proceedings of The 37th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 313:1-18 Available from https://proceedings.mlr.press/v313/larsen26b.html.

Related Material