Boosting with List-Decodable Codes

Addison Prairie, Li-Yang Tan
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:5377-5396, 2026.

Abstract

Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-\textsc{Xor}, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\Tilde{O}(\log(\frac{1}{\epsilon})/\gamma^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-prairie26a, title = {Boosting with List-Decodable Codes}, author = {Prairie, Addison and Tan, Li-Yang}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {5377--5396}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/prairie26a/prairie26a.pdf}, url = {https://proceedings.mlr.press/v336/prairie26a.html}, abstract = {Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-\textsc{Xor}, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\Tilde{O}(\log(\frac{1}{\epsilon})/\gamma^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.} }
Endnote
%0 Conference Paper %T Boosting with List-Decodable Codes %A Addison Prairie %A Li-Yang Tan %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-prairie26a %I PMLR %P 5377--5396 %U https://proceedings.mlr.press/v336/prairie26a.html %V 336 %X Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-\textsc{Xor}, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\Tilde{O}(\log(\frac{1}{\epsilon})/\gamma^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.
APA
Prairie, A. & Tan, L.. (2026). Boosting with List-Decodable Codes. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:5377-5396 Available from https://proceedings.mlr.press/v336/prairie26a.html.

Related Material