New boosting algorithm cuts round complexity via list-decodable codes

Classical boosting, pioneered by Schapire, builds a strong learner by sequentially calling a weak learner that always beats random guessing by a margin γ. The number of calls required is known to be O(log(1/ε)/γ²) – and this round complexity was proven optimal for generic boosters that work on any concept class, a lower bound established by Freund. Prairie and Tan show this barrier can be broken for classes that satisfy a mild closure property: being closed under O(log(1/γ))-XOR (i.e., XOR of up to that many functions from the class).

Their algorithm creates a simple connection between boosting and list-decodable codes. The core idea: view the target concept as a message, encode it using a code with good list-decodability, then run the weak learner on the encoding. The weak hypothesis becomes a corrupted codeword. Running a list decoder on this yields a small list of candidate hypotheses, one of which is guaranteed to be a strong hypothesis for the original function. A final batch of Õ(log(1/ε)/γ²) additional samples identifies the correct hypothesis. The result cuts the number of weak learner calls to O(log(1/ε)), independent of γ, while only requiring a one-time extra sample budget. This theoretical advance opens new avenues for designing more sample- and call-efficient boosting algorithms in practice.