QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses

Amira Abbas, Yanlin Chen, Tuyen Quang Nguyen, Ronald De Wolf
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:69-83, 2026.

Abstract

The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple "weak learners"—hypotheses that are only slightly better than random guessing—into a single "strong learner" that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-abbas26a, title = {{Q}uantum{B}oost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses}, author = {Abbas, Amira and Chen, Yanlin and Nguyen, Tuyen Quang and De Wolf, Ronald}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {69--83}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/abbas26a/abbas26a.pdf}, url = {https://proceedings.mlr.press/v306/abbas26a.html}, abstract = {The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple "weak learners"—hypotheses that are only slightly better than random guessing—into a single "strong learner" that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.} }
Endnote
%0 Conference Paper %T QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses %A Amira Abbas %A Yanlin Chen %A Tuyen Quang Nguyen %A Ronald De Wolf %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-abbas26a %I PMLR %P 69--83 %U https://proceedings.mlr.press/v306/abbas26a.html %V 306 %X The technique of combining multiple votes to enhance the quality of a decision is the core of boosting algorithms in machine learning. In particular, boosting provably increases decision quality by combining multiple "weak learners"—hypotheses that are only slightly better than random guessing—into a single "strong learner" that classifies data well. There exist various versions of boosting algorithms, which we improve upon through the introduction of QuantumBoost. Inspired by classical work by Barak, Hardt and Kale, our QuantumBoost algorithm achieves the best known runtime over other boosting methods through two innovations. First, it uses a quantum algorithm to compute approximate Bregman projections faster. Second, it combines this with a lazy projection strategy, a technique from convex optimization where projections are performed infrequently rather than every iteration. To our knowledge, QuantumBoost is the first algorithm, classical or quantum, to successfully adopt a lazy projection strategy in the context of boosting.
APA
Abbas, A., Chen, Y., Nguyen, T.Q. & De Wolf, R.. (2026). QuantumBoost: A lazy, yet fast, quantum algorithm for learning with weak hypotheses. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:69-83 Available from https://proceedings.mlr.press/v306/abbas26a.html.

Related Material