📊 statistics

Boosting with List-Decodable Codes

This paper introduces a boosting algorithm that circumvents the standard $O(\log(1/\epsilon)/\gamma^2)$ round complexity lower bound for concept classes closed under limited XOR operations by leveraging a novel connection to list-decodable codes to achieve $O(\log(1/\epsilon))$ rounds with a single batch of additional samples.

Original authors: Addison Prairie, Li-Yang Tan

Published 2026-07-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Addison Prairie, Li-Yang Tan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to recognize cats. You have a "weak teacher" who is only slightly better than a coin flip at spotting cats. Maybe they get it right 55% of the time, but they are terrible at distinguishing cats from dogs or toaster ovens.

Boosting is the standard method for turning this weak teacher into a genius. The traditional way works like a game of "Hot and Cold." You ask the weak teacher to guess on a bunch of pictures. When they get it wrong, you shout, "No! Look harder at these specific pictures!" You then feed them a new batch of pictures where the mistakes were most common. You repeat this process over and over, asking the teacher to focus on their weaknesses. Eventually, by combining all their guesses, you get a perfect expert.

However, there's a catch. To get that perfect expert, the traditional method requires you to ask the weak teacher to guess on thousands of different batches of data. It's a long, exhausting conversation.

The New Approach: The "List-Decodable Code" Trick

This paper introduces a clever shortcut. Instead of having the weak teacher focus on specific mistakes one by one, the authors change the game entirely. They use a concept from cryptography called List-Decodable Codes.

Here is the analogy:

The Message and the Encoding: Imagine the true answer (the "cat") is a secret message. Instead of showing the weak teacher the message directly, you scramble it using a special code (like turning a sentence into a complex puzzle).
The Corrupted Clue: You show the weak teacher this scrambled puzzle. Because the teacher is only slightly smart, they can't solve the whole puzzle perfectly. They give you a "corrupted" version of the solution.
The Magic Decoder: Here is the magic trick. In the old method, a corrupted solution was useless. But in this new method, the authors use a special Decoder. Even if the teacher's solution is messy and wrong, the Decoder knows that the correct answer must be hiding somewhere in a very short list of possibilities.
- Think of it like this: If you ask a slightly confused friend to describe a movie you both watched, and they get the plot wrong, you might not know the ending. But if you have a "Decoder" that knows the movie is one of only three famous films, the friend's confused description might be enough to narrow it down to a list of just three candidates.
The Final Check: The Decoder gives you a short list of 3 or 4 possible answers. You then use a small, fresh batch of data to quickly check which one of those few candidates is actually the right one.

Why This Matters

The paper claims that for certain types of problems (specifically those where you can mix and match features in a specific way, called "XOR closure"), this new method is much more efficient.

Old Way: You talk to the weak teacher thousands of times (thousands of "rounds").
New Way: You talk to the weak teacher only once (or very few times). You ask them to solve a slightly harder, scrambled version of the problem. Then, you do a little bit of extra work (checking a short list) to find the right answer.

The Trade-Off

Is there a cost? Yes.

The Old Way: The teacher looks at simple pictures, but you have to talk to them a lot.
The New Way: You ask the teacher to look at a "super-complex" picture (which is actually a combination of many simple pictures). This takes the teacher a bit more time and memory to process once, but you save yourself the trouble of having to ask them thousands of times.

The Bottom Line

The authors show that if your learning problem has a specific mathematical structure (like being able to combine features easily), you don't need to have a long, repetitive conversation with a weak learner to get a strong result. Instead, you can ask them one big, slightly complex question, use a "decoder" to generate a short list of likely answers, and pick the winner. This saves a massive amount of time and interaction, making the learning process much faster for the right kinds of problems.

Technical Summary: Boosting with List-Decodable Codes

Problem Statement

Boosting is a fundamental technique for converting a "weak learner" (an algorithm that achieves accuracy slightly better than random guessing, $1/2 + \gamma$ ) into a "strong learner" (an algorithm achieving arbitrarily high accuracy, $1-\epsilon$ ). A central metric of boosting efficiency is round complexity, defined as the number of calls made to the weak learner.

Existing boosting algorithms (e.g., AdaBoost) require $O(\log(1/\epsilon)/\gamma^2)$ calls to the weak learner. Freund (1995) established that this round complexity is optimal for generic boosters that succeed on all concept classes. However, the concept class used to prove this lower bound is highly artificial (consisting of a single random function), leaving open the possibility that more structured concept classes might admit more round-efficient boosting.

This paper addresses the question: Can the $O(\log(1/\epsilon)/\gamma^2)$ lower bound on round complexity be circumvented for concept classes satisfying a mild structural closure property?

Methodology

The authors propose a new boosting framework that fundamentally shifts the approach from reweighting distributions (the standard method) to modifying the function being learned. This approach relies on a novel connection between boosting and list-decodable error-correcting codes.

The Core Framework

Encoding the Target: Instead of reweighting the distribution of samples fed to the weak learner, the algorithm encodes the target function $f$ into a new function $f' = \text{Enc}(f)$ .
Weak Learning on the Encoding: The weak learner $W$ is called once (or a few times) on the encoded function $f'$ . It produces a hypothesis $h'$ that weakly computes $f'$ .
List Decoding: The hypothesis $h'$ is viewed as a corrupted codeword. A list-decoding algorithm is applied to $h'$ to generate a short list of candidate hypotheses $\{h_1, \dots, h_L\}$ .
Selection: Using a small batch of additional labeled samples, the algorithm tests the candidates in the list to identify and output the one that strongly computes the original function $f$ .

The Specific Code: $k$ -XOR

The authors instantiate this framework using the $k$ -XOR code. For a function $f: X \to \{\pm 1\}$ , the encoding is $f^{\oplus k}: X^k \to \{\pm 1\}$ , defined as:
$f^{\oplus k}(x_1, \dots, x_k) = f(x_1) \oplus \dots \oplus f(x_k)$
The concept class $\mathcal{F}$ is assumed to be closed under $k$ -XOR, meaning if $f \in \mathcal{F}$ , then $f^{\oplus k} \in \mathcal{F}$ (specifically, in the appropriate slice of the class).

To handle arbitrary distributions and potentially infinite domains, the authors generalize the concept of error-correcting codes to distributional codes, where error and corruption are measured with respect to specific distributions over the input space and the codeword space. They construct an efficient distributional local list decoder for the $k$ -Xor code, generalizing previous work by Impagliazzo, Jaiswal, Kabanets, and Wigderson (IJKW10) to continuous and distributional settings.

Key Contributions and Results

1. Improved Round Complexity for Closed Classes

The primary result (Theorem 1) demonstrates that for any concept class $\mathcal{F}$ closed under $O(\log(1/\gamma))$ -XOR, there exists an efficient boosting algorithm that:

Makes $O(\log(1/\epsilon))$ calls to the weak learner (a significant improvement over the generic $O(\log(1/\epsilon)/\gamma^2)$ ).
Uses $\tilde{O}(\log(1/\epsilon)/\gamma^2)$ additional labeled samples.
Trade-off: While the number of calls is reduced, each call operates on a function over a larger domain ( $X^k$ instead of $X$ ). However, if the weak learner runs in polynomial time, this results in only a modest $\text{polylog}(1/\gamma)$ increase in resources per call.

2. Uniform-Distribution Boosting with Single Call

For the specific setting of learning over the uniform distribution (Theorem 2), the authors present an algorithm that:

Makes only 1 call to a uniform-distribution weak learner.
Requires the concept class to be closed under $O(\log(1/\gamma)/\epsilon)$ -XOR.
Uses $\tilde{O}(\log(1/\gamma)/\epsilon)$ additional labeled samples.
This result is notable because it achieves strong learning with a single round of interaction, provided the weak learner is specific to the uniform distribution.

3. Mildness of Assumptions

The closure assumption is mild. In the standard weak learning setting where $\gamma = n^{-O(1)}$ , the algorithm only requires closure under $O(\log n)$ -XOR. Since the XOR of $O(\log n)$ bits can be computed by polynomial-sized DNF/CNF formulas, this boosting algorithm applies to a broad range of concept classes, including computationally weaker classes like small, constant-depth circuits (e.g., $AC^0$ ), which were previously excluded by stronger closure requirements in related work (e.g., Boneh and Lipton, 1993).

Significance and Claims

The paper claims to circumvent Freund's lower bound not by violating the mathematical constraints of generic boosting, but by restricting the scope to concept classes with a specific algebraic structure (closure under XOR).

Theoretical Impact: The work establishes a direct, simple connection between boosting and list-decodable codes, offering a new paradigm for boosting that avoids the iterative distribution reweighting of traditional methods.
Practical Implications: The results suggest that for structured classes (like those closed under low-degree XOR), one can achieve strong learning with significantly fewer rounds of interaction with a weak learner, provided one is willing to process slightly larger input spaces per round.
Comparison to Prior Work:
- Unlike Alon et al. (2021), which achieves low round complexity but requires exponential time in $1/\gamma$ , this algorithm remains efficient (polynomial time).
- Unlike Boneh and Lipton (1993), which required closure under $O(1/\gamma^2\epsilon)$ -XOR, this work requires only $O(\log(1/\gamma))$ -XOR, making it applicable to a far broader range of parameters and concept classes.
- Unlike agnostic boosting approaches (Kalai and Kanade, 2009; Feldman, 2009) that assume the weak learner is noise-tolerant, this approach places the assumption on the concept class structure rather than the learner's robustness.

In summary, the paper demonstrates that by leveraging list-decodable codes and mild closure properties, the round complexity of boosting can be reduced from $O(1/\gamma^2)$ to $O(1)$ (or $O(\log(1/\epsilon))$ depending on the setting), fundamentally changing the resource trade-off from "many calls on small domains" to "fewer calls on slightly expanded domains."