🤖 machine learning

A Rate Separation for Agnostic Direct Sums

This paper demonstrates that the agnostic PAC learning rate of a direct sum of concept classes is not solely determined by the single-instance learning rates of its components, as shown by constructing two classes with identical $n^{-1/2}$ learning curves that yield different rates when combined.

Original authors: Mihir More, Aritra Das, Debayan Gupta

Published 2026-08-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mihir More, Aritra Das, Debayan Gupta

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 a world where machines learn by playing a guessing game. In the field of computer science known as "machine learning," we often ask: how many examples does a computer need to get really good at a task? This is the study of "learning curves." Think of it like training a puppy. If you want a puppy to learn to sit, you might need ten treats. If you want it to learn to roll over, you might need twenty. The "learning curve" is just a graph showing how the puppy's mistakes drop as it eats more treats.

Now, imagine you have a super-puppy that doesn't just learn one trick, but a whole bundle of tricks at once. Maybe it has to learn to sit, roll over, and bark all in the same session. In math, this is called a "direct sum." You take a simple learning problem and multiply it by itself many times to create a bigger, more complex challenge. For a long time, scientists wondered if the difficulty of this big bundle was just a simple math problem: if you know how hard the single trick is, and you know how many tricks you are bundling, can you just do the math to know how hard the whole bundle will be? It seemed logical that if one trick is easy, ten tricks should just be ten times as hard, or maybe a little harder. But as we are about to see, the universe of learning is full of surprises, and sometimes, the whole is very different from the sum of its parts.

This paper, titled "A Rate Separation for Agnostic Direct Sums," dives into that exact question. The authors, Mihir More, Aritra Das, and Debayan Gupta, set out to test a popular idea: that the speed at which a machine learns a single task (the "single-instance learning rate") completely determines how fast it will learn a bundle of those tasks (the "direct-sum rate"). They wanted to see if knowing the learning speed of one problem was enough to predict the learning speed of a massive, combined version of that problem.

The researchers discovered that the answer is a firm "no." They proved that two completely different learning problems can look identical when you test them one by one, but once you bundle them together, they behave in totally opposite ways. To show this, they created two fictional "concept classes" (which are just sets of rules the machine tries to learn). Let's call them the "Constant Class" and the "Identity Class."

The first class, the "Constant Class," is like a broken clock that always says the same time, no matter what. The machine just has to guess which constant time it is. The second class, the "Identity Class," is like a mirror; whatever input you give it, it just copies it back. When the machine tries to learn just one of these rules, both are equally easy. They both follow a learning curve where the mistakes drop at a rate of $n^{-1/2}$ (which means if you double your practice data, you get a bit better, but not twice as good). It's a standard, predictable pace.

However, the plot twists when the authors bundle these rules together. They created a "direct sum" by taking 100 copies of the Constant Class and 100 copies of the Identity Class and asking the machine to learn them all at once. Here is where the magic happens: the bundle of Constants stayed easy, keeping that same steady learning pace. But the bundle of Identities became a nightmare. As the number of copies ( $r$ ) grew, the learning curve for the Identity bundle slowed down dramatically, becoming much harder to learn than the Constant bundle.

The paper proves mathematically that for the Identity bundle, the learning rate depends heavily on the number of copies in a way the Constant bundle does not. Specifically, when the number of copies ( $r$ ) is large, the error rate for the Identity bundle stays stubbornly high, refusing to drop as fast as the Constant bundle does. In fact, if you have enough copies, the machine might get stuck at a high error rate no matter how much data you give it, whereas the Constant bundle keeps improving.

The authors used rigorous mathematical tools, including a famous lemma called "Assouad's lemma" and a technique called "Le Cam's two-point inequality," to build an unbreakable proof. They didn't just simulate this on a computer; they showed that this separation is a fundamental law of learning theory. They demonstrated that you cannot simply look at how fast a machine learns one thing and assume you know how fast it will learn a hundred of those things. The structure of the rules matters just as much as the number of rules.

In the end, this paper pulls the rug out from under a simple assumption. It tells us that in the world of machine learning, context is king. Two problems that look the same in isolation can behave like oil and water when mixed together. The speed of learning a single task is not a crystal ball for the speed of learning a complex system. The authors have shown that the relationship between single-instance learning and direct-sum learning is far more mysterious and complex than anyone had previously realized, proving that in the grand game of learning, the whole is definitely not just the sum of its parts.

Technical Summary: A Rate Separation for Agnostic Direct Sums

Problem Statement
The paper addresses a fundamental question in agnostic PAC learning regarding the behavior of direct sums of concept classes. Specifically, it investigates whether the agnostic learning curve of an $r$ -fold direct sum, denoted $C^r$ , is determined solely by the single-instance learning curve $\varepsilon_{\text{agn}}(n \mid C)$ and the number of factors $r$ . This question was posed by Hanneke, Moran, and Waknine [HMW24]. The core inquiry is whether the order of the learning rate for a single instance, combined with the number of copies, suffices to predict the learning rate of the product class under the unrestricted, distribution-free setting.

Methodology and Setup
The authors utilize the standard agnostic PAC learning framework where the goal is to minimize excess risk relative to the best member of a concept class $C$ .

Direct Sum Definition: For classes $C_1 \subseteq Y^{X_1}$ and $C_2 \subseteq Y^{X_2}$ , the direct sum $C_1 \otimes C_2$ consists of functions $(c_1 \otimes c_2)(x_1, x_2) = (c_1(x_1), c_2(x_2))$ . The $r$ -fold direct sum is $C^r = \bigotimes_{i=1}^r C$ .
Loss Function: The loss is defined as the zero-one loss on the full output vector, not coordinate-wise Hamming loss.
Learning Curve: The agnostic learning curve is defined as $\varepsilon_{\text{agn}}(n \mid C) = \inf_A \sup_D (L_{D,n}(A) - L_D(C))$ , where the infimum is over learning rules and the supremum is over all distributions.

To resolve the problem, the authors construct two specific concept classes, $F$ and $G$ , over the domain and label space $X = Y = \{0, 1\}$ :

Class $F$ : Contains the two constant binary functions ( $f_0(x)=0, f_1(x)=1$ ).
Class $G$ : Contains the zero function and the identity function ( $g_0(x)=0, g_1(x)=x$ ).

The authors prove that while both classes exhibit the same single-instance learning rate, their $r$ -fold direct sums exhibit fundamentally different learning rates.

Key Contributions and Results

Single-Instance Equivalence:
The paper establishes that both $F$ and $G$ have an agnostic learning curve of order $n^{-1/2}$ .
- For $F$ , the result follows from the standard analysis of constant functions and empirical risk minimization.
- For $G$ , the result is derived by taking $r=1$ in the main theorem (Theorem 1), which yields $\varepsilon_{\text{agn}}(n \mid G) \asymp n^{-1/2}$ .
Rate Separation in Direct Sums (The Main Theorem):
The central contribution is Theorem 1, which demonstrates a "rate separation" between the direct sums $F^r$ and $G^r$ :
- For $F^r$ (Constant Class): The learning rate remains $\Theta(n^{-1/2})$ regardless of $r$ . The proof shows that the excess risk is governed by the estimation error of the most probable constant vector, which scales as $1/\sqrt{n}$ .
- For $G^r$ (Zero/Identity Class): The learning rate scales as $\Theta(\min\{1, \sqrt{r/n}\})$ $Θ (min {1, r / n})$ .
  - When $r \le n$ , the rate is $\Theta(\sqrt{r/n})$ .
  - When $r > n$ , the minimax excess risk is bounded below by a positive constant (i.e., learning is impossible in the limit).
Consequently, while $\varepsilon_{\text{agn}}(n \mid F) \asymp \varepsilon_{\text{agn}}(n \mid G)$ , the asymptotic orders of $\varepsilon_{\text{agn}}(n \mid F^r)$ and $\varepsilon_{\text{agn}}(n \mid G^r)$ diverge as $r$ grows.
Proof Techniques:
- Upper Bounds: Derived using standard empirical risk minimization bounds for finite classes. For $G^r$ , the bound utilizes the fact that $|G^r| = 2^r$ , leading to a term proportional to $\sqrt{\frac{r \log 2}{n}}$ .
- Lower Bounds: Established using information-theoretic tools.
  - For $F^r$ , a two-point Le Cam method is used to show the difficulty of distinguishing between two dominant constant labels.
  - For $G^r$ , the authors employ Assouad's Lemma combined with Pinsker's inequality. They construct a family of distributions parameterized by $\theta \in \{-1, +1\}^r$ . In this construction, an input coordinate $J$ is chosen uniformly from $\{1, \dots, r\}$ , setting $X = e_J$ . Conditional on $J=j$ , the label $Y$ is $e_j$ with probability $1/2 + \theta_j \alpha$ and $0^r$ with probability $1/2 - \theta_j \alpha$ . The proof relates the Hamming distance of estimating $\theta$ to the excess risk, showing that estimating the $r$ -dimensional parameter vector requires a sample size proportional to $r$ .

Significance and Claims
The paper provides a negative answer to the rate-level form of the question posed by [HMW24]. It claims that the single-instance learning rate and the number of factors $r$ are not sufficient to determine the asymptotic order of the learning curve for the direct sum $C^r$ .

The authors note that while subsequent works (e.g., [Sur24], [HMS26]) have studied direct sums under different complexity frameworks or structural distributional assumptions, and recent work on multiclass learning provides combinatorial bounds, none of these results express the direct-sum curve as a function of the single-instance curve alone in the unrestricted distribution-free setting. This paper explicitly resolves that gap by exhibiting a counterexample where the structural properties of the class (constant vs. identity) lead to divergent behaviors in the product space, despite identical single-instance performance.

The conclusion emphasizes that for arbitrary concept classes, knowledge of $\varepsilon_{\text{agn}}(n \mid C)$ and $r$ does not allow one to predict $\varepsilon_{\text{agn}}(n \mid C^r)$ . Specifically, for $G^r$ , the risk can remain bounded away from zero when $r \ge n$ , whereas for $F^r$ , it continues to decay as $n^{-1/2}$ .

Technical Summary: A Rate Separation for Agnostic Direct Sums

More like this