A Rate Separation for Agnostic Direct Sums

# A Rate Separation for Agnostic Direct Sums
Source: [https://arxiv.org/html/2608.06951](https://arxiv.org/html/2608.06951)
###### Abstract

Hanneke, Moran, and Waknine\[[HMW24](https://arxiv.org/html/2608.06951#bib.bib4)\]asked how the agnostic PAC learning curve of the direct sumCrC^\{r\}depends on the single\-instance learning curveεagn​\(n∣C\)\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C\)and onrr\. We show that the single\-instance learning rate does not determine the direct\-sum rate\. Letℱ\\mathcal\{F\}be the class of the two constant binary functions and let𝒢\\mathcal\{G\}consist of the zero function and the identity function\. Both classes have agnostic learning curve of ordern−1/2n^\{\-1/2\}\.

## 1Introduction

LetC1⊆𝒴1𝒳1C\_\{1\}\\subseteq\\mathcal\{Y\}\_\{1\}^\{\\mathcal\{X\}\_\{1\}\}andC2⊆𝒴2𝒳2C\_\{2\}\\subseteq\\mathcal\{Y\}\_\{2\}^\{\\mathcal\{X\}\_\{2\}\}be concept classes\. Following Hanneke, Moran, and Waknine\[[HMW24](https://arxiv.org/html/2608.06951#bib.bib4)\], their direct sumC1⊗C2C\_\{1\}\\otimes C\_\{2\}is the class of functions

\(c1⊗c2\)​\(x1,x2\)=\(c1​\(x1\),c2​\(x2\)\),ci∈Ci\.\(c\_\{1\}\\otimes c\_\{2\}\)\(x\_\{1\},x\_\{2\}\)=\\bigl\(c\_\{1\}\(x\_\{1\}\),c\_\{2\}\(x\_\{2\}\)\\bigr\),\\qquad c\_\{i\}\\in C\_\{i\}\.For a classCC, itsrr\-fold direct sum is denoted by

Cr=⨂i=1rC\.C^\{r\}=\\bigotimes\_\{i=1\}^\{r\}C\.
The agnostic learning curve measures excess risk relative to the best member ofCrC^\{r\}\. An upper bound on the risk of a product hypothesis does not directly control this excess risk\. This is noted in\[[HMW24](https://arxiv.org/html/2608.06951#bib.bib4)\]\. We give a negative answer to the rate\-level form of the question, the order ofεagn​\(n∣C\)\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C\)and the number of factors do not determine the order ofεagn​\(n∣Cr\)\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C^\{r\}\)\. To the best of our knowledge, no subsequent paper explicitly resolves this question in its unrestricted distribution\-free form\. Suruga\[[SUR24](https://arxiv.org/html/2608.06951#bib.bib8)\]proves direct\-sum theorems in a different complexity framework, and Holzman, Moran, and Shlimovich\[[HMS26](https://arxiv.org/html/2608.06951#bib.bib5)\]study uniform laws of large numbers in product spaces under structural assumptions on the distribution\. Recent work on agnostic multiclass learning gives class\-specific sample\-complexity bounds in terms of combinatorial dimensions\[[CEH\+25](https://arxiv.org/html/2608.06951#bib.bib2),[PAB26](https://arxiv.org/html/2608.06951#bib.bib7)\]\. These results are consistent with the separation proved here but do not express the direct\-sum curve as a function of the single\-instance learning curve alone\.

## 2Preliminaries

We use the setup and notation of\[[HMW24](https://arxiv.org/html/2608.06951#bib.bib4)\]\. Let𝒳\\mathcal\{X\}be a domain, let𝒴\\mathcal\{Y\}be a label space, and letk≥1k\\geq 1\. Write

\(𝒴k\)=\{B⊆𝒴:\|B\|=k\}\.\\binom\{\\mathcal\{Y\}\}\{k\}=\\\{B\\subseteq\\mathcal\{Y\}:\|B\|=k\\\}\.Akk\-list function is a mapc:𝒳→\(𝒴k\)c:\\mathcal\{X\}\\to\\binom\{\\mathcal\{Y\}\}\{k\}, and akk\-list concept class is a set

C⊆\(𝒴k\)𝒳\.C\\subseteq\\binom\{\\mathcal\{Y\}\}\{k\}^\{\\mathcal\{X\}\}\.Akk\-list learning rule is a map

A:\(𝒳×𝒴\)∗⟶\(𝒴k\)𝒳\.A:\(\\mathcal\{X\}\\times\\mathcal\{Y\}\)^\{\*\}\\longrightarrow\\binom\{\\mathcal\{Y\}\}\{k\}^\{\\mathcal\{X\}\}\.For a distributionDDon𝒳×𝒴\\mathcal\{X\}\\times\\mathcal\{Y\}, the population loss of akk\-list functionccis

LD​\(c\)=𝔼\(x,y\)∼D​\[𝟏​\{y∉c​\(x\)\}\]\.L\_\{D\}\(c\)=\\mathbb\{E\}\_\{\(x,y\)\\sim D\}\\bigl\[\\mathbf\{1\}\\\{y\\notin c\(x\)\\\}\\bigr\]\.\(1\)
Whenk=1k=1, we identify a singleton\{y\}\\\{y\\\}with its unique elementyy\. Under this identification, a11\-list function is an ordinary functionc:𝒳→𝒴c:\\mathcal\{X\}\\to\\mathcal\{Y\}, and a11\-list concept class is an ordinary concept classC⊆𝒴𝒳C\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}\. This is precisely the case considered in\[[HMW24](https://arxiv.org/html/2608.06951#bib.bib4)\]\. We therefore setk=1k=1from this point onward\. The loss in \([1](https://arxiv.org/html/2608.06951#S2.E1)\) becomes

LD​\(h\)=𝔼\(x,y\)∼D​\[𝟏​\{h​\(x\)≠y\}\]\.L\_\{D\}\(h\)=\\mathbb\{E\}\_\{\(x,y\)\\sim D\}\\bigl\[\\mathbf\{1\}\\\{h\(x\)\\neq y\\\}\\bigr\]\.ForC⊆𝒴𝒳C\\subseteq\\mathcal\{Y\}^\{\\mathcal\{X\}\}, write

LD​\(C\)=infc∈CLD​\(c\)\.L\_\{D\}\(C\)=\\inf\_\{c\\in C\}L\_\{D\}\(c\)\.IfAAis a learning rule andS∼DnS\\sim D^\{n\}, define

LD,n​\(A\)=𝔼S∼Dn​\[LD​\(A​\(S\)\)\]\.L\_\{D,n\}\(A\)=\\mathbb\{E\}\_\{S\\sim D^\{n\}\}\\bigl\[L\_\{D\}\(A\(S\)\)\\bigr\]\.The agnostic PAC learning curve is

εagn​\(n∣C\)=infAsupD\(LD,n​\(A\)−LD​\(C\)\),\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C\)=\\inf\_\{A\}\\sup\_\{D\}\\bigl\(L\_\{D,n\}\(A\)\-L\_\{D\}\(C\)\\bigr\),\(2\)where the supremum is over all distributions on𝒳×𝒴\\mathcal\{X\}\\times\\mathcal\{Y\}\. The learning rule is not required to output a member ofCC\.

For concept classesCi⊆𝒴i𝒳iC\_\{i\}\\subseteq\\mathcal\{Y\}\_\{i\}^\{\\mathcal\{X\}\_\{i\}\}, their direct sum is

C1⊗C2=\{c1⊗c2:ci∈Ci\},\(c1⊗c2\)​\(x1,x2\)=\(c1​\(x1\),c2​\(x2\)\)\.C\_\{1\}\\otimes C\_\{2\}=\\\{c\_\{1\}\\otimes c\_\{2\}:c\_\{i\}\\in C\_\{i\}\\\},\\qquad\(c\_\{1\}\\otimes c\_\{2\}\)\(x\_\{1\},x\_\{2\}\)=\\bigl\(c\_\{1\}\(x\_\{1\}\),c\_\{2\}\(x\_\{2\}\)\\bigr\)\.Forr≥1r\\geq 1, we writeCr=⨂i=1rCC^\{r\}=\\bigotimes\_\{i=1\}^\{r\}C\. Its domain is𝒳r\\mathcal\{X\}^\{r\}, its label space is𝒴r\\mathcal\{Y\}^\{r\}, and its loss is zero\-one loss on the full vector:

LD​\(h\)=ℙ\(x,y\)∼D​\(h​\(x\)≠y\)\.L\_\{D\}\(h\)=\\mathbb\{P\}\_\{\(x,y\)\\sim D\}\\bigl\(h\(x\)\\neq y\\bigr\)\.In particular, this is not coordinatewise Hamming loss\.

We writean,r≍bn,ra\_\{n,r\}\\asymp b\_\{n,r\}if there are universal constantsc,C\>0c,C\>0such that

c​bn,r≤an,r≤C​bn,rcb\_\{n,r\}\\leq a\_\{n,r\}\\leq Cb\_\{n,r\}for all relevantnnandrr\.

We use four standard facts\. First, empirical risk minimization over a finite classHHsatisfies

εagn​\(n∣H\)≤K​min⁡\{1,log⁡\|H\|n\}\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid H\)\\leq K\\min\\left\\\{1,\\sqrt\{\\frac\{\\log\|H\|\}\{n\}\}\\right\\\}\(3\)for a universal constantKK; see\[[DGL96](https://arxiv.org/html/2608.06951#bib.bib3), Chapter 12\]\. Second, Le Cam’s two\-point inequality states that, for distributionsP\+P\_\{\+\}andP−P\_\{\-\}and any testσ^\\widehat\{\\sigma\}taking values in\{−1,\+1\}\\\{\-1,\+1\\\},

maxσ∈\{−1,\+1\}⁡Pσ​\(σ^≠σ\)≥1−TV⁡\(P\+,P−\)2;\\max\_\{\\sigma\\in\\\{\-1,\+1\\\}\}P\_\{\\sigma\}\(\\widehat\{\\sigma\}\\neq\\sigma\)\\geq\\frac\{1\-\\operatorname\{TV\}\(P\_\{\+\},P\_\{\-\}\)\}\{2\};\(4\)see\[[TSY09](https://arxiv.org/html/2608.06951#bib.bib9), Chapter 2\]\. Third, Pinsker’s inequality gives

TV⁡\(P,Q\)≤12​KL⁡\(P∥Q\)\.\\operatorname\{TV\}\(P,Q\)\\leq\\sqrt\{\\frac\{1\}\{2\}\\operatorname\{KL\}\(P\\\|Q\)\}\.\(5\)Finally, we use the following standard form of Assouad’s lemma\. Forθ∈\{−1,\+1\}r\\theta\\in\\\{\-1,\+1\\\}^\{r\}, letθ\(j\)\\theta^\{\(j\)\}be obtained fromθ\\thetaby changing the sign of itsjjth coordinate, and define

dH​\(a,b\)=∑j=1r𝟏​\{aj≠bj\}\.d\_\{\\mathrm\{H\}\}\(a,b\)=\\sum\_\{j=1\}^\{r\}\\mathbf\{1\}\\\{a\_\{j\}\\neq b\_\{j\}\\\}\.
###### Lemma 1\(Assouad’s lemma;\[[ASS83](https://arxiv.org/html/2608.06951#bib.bib1),[TSY09](https://arxiv.org/html/2608.06951#bib.bib9)\]\)\.

Let\{Pθ:θ∈\{−1,\+1\}r\}\\\{P\_\{\\theta\}:\\theta\\in\\\{\-1,\+1\\\}^\{r\}\\\}be a family of distributions on a common measurable space\. If

TV⁡\(Pθ,Pθ\(j\)\)≤η\\operatorname\{TV\}\(P\_\{\\theta\},P\_\{\\theta^\{\(j\)\}\}\)\\leq\\etafor everyθ\\thetaandjj, then every estimatorθ^\\widehat\{\\theta\}with values in\{−1,\+1\}r\\\{\-1,\+1\\\}^\{r\}satisfies

supθ∈\{−1,\+1\}r𝔼θ​\[dH​\(θ^,θ\)\]≥r2​\(1−η\)\.\\sup\_\{\\theta\\in\\\{\-1,\+1\\\}^\{r\}\}\\mathbb\{E\}\_\{\\theta\}\\bigl\[d\_\{\\mathrm\{H\}\}\(\\widehat\{\\theta\},\\theta\)\\bigr\]\\geq\\frac\{r\}\{2\}\(1\-\\eta\)\.

## 3Main result

Set𝒳=𝒴=\{0,1\}\\mathcal\{X\}=\\mathcal\{Y\}=\\\{0,1\\\}\. Define

ℱ\\displaystyle\\mathcal\{F\}=\{f0,f1\},\\displaystyle=\\\{f\_\{0\},f\_\{1\}\\\},fb​\(x\)\\displaystyle f\_\{b\}\(x\)=b,\\displaystyle=b,𝒢\\displaystyle\\mathcal\{G\}=\{g0,g1\},\\displaystyle=\\\{g\_\{0\},g\_\{1\}\\\},gb​\(x\)\\displaystyle g\_\{b\}\(x\)=b​x\.\\displaystyle=bx\.Thusℱ\\mathcal\{F\}consists of the two constant binary functions, while𝒢\\mathcal\{G\}consists of the zero function and the identity function\.

###### Theorem 1\(Rate separation\)\.

There are universal constants0<c<C<∞0<c<C<\\inftysuch that, for alln,r≥1n,r\\geq 1,

cn\\displaystyle\\frac\{c\}\{\\sqrt\{n\}\}≤εagn​\(n∣ℱr\)≤Cn,\\displaystyle\\leq\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{F\}^\{r\}\)\\leq\\frac\{C\}\{\\sqrt\{n\}\},\(6\)c​min⁡\{1,rn\}\\displaystyle c\\min\\left\\\{1,\\sqrt\{\\frac\{r\}\{n\}\}\\right\\\}≤εagn​\(n∣𝒢r\)≤C​min⁡\{1,rn\}\.\\displaystyle\\leq\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{G\}^\{r\}\)\\leq C\\min\\left\\\{1,\\sqrt\{\\frac\{r\}\{n\}\}\\right\\\}\.\(7\)Consequently,

εagn​\(n∣ℱ\)≍εagn​\(n∣𝒢\)≍n−1/2,\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{F\}\)\\asymp\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{G\}\)\\asymp n^\{\-1/2\},but the rates of their direct sums differ asrrgrows\.

The single\-instance statement follows by takingr=1r=1in \([6](https://arxiv.org/html/2608.06951#S3.E6)\) and \([7](https://arxiv.org/html/2608.06951#S3.E7)\)\. The main assertion is that the two rates cease to agree after taking direct sums\. We prove \([6](https://arxiv.org/html/2608.06951#S3.E6)\) and \([7](https://arxiv.org/html/2608.06951#S3.E7)\) in the next two sections\.

### 3\.1Direct sums of the constant class

A hypothesis inℱr\\mathcal\{F\}^\{r\}is indexed byu=\(u1,…,ur\)∈\{0,1\}ru=\(u\_\{1\},\\ldots,u\_\{r\}\)\\in\\\{0,1\\\}^\{r\}and predictsuuat every input\. Write this hypothesis ashuh\_\{u\}\. For a distributionDDon𝒳r×𝒴r\\mathcal\{X\}^\{r\}\\times\\mathcal\{Y\}^\{r\}, define

pu=ℙD​\(Y=u\),p^u=1n​∑i=1n𝟏​\{Yi=u\}\.p\_\{u\}=\\mathbb\{P\}\_\{D\}\(Y=u\),\\qquad\\widehat\{p\}\_\{u\}=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{Y\_\{i\}=u\\\}\.\(8\)Let

u⋆∈arg​maxu∈\{0,1\}r⁡pu,u^∈arg​maxu∈\{0,1\}r⁡p^u\.u^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{u\\in\\\{0,1\\\}^\{r\}\}p\_\{u\},\\qquad\\widehat\{u\}\\in\\operatorname\*\{arg\\,max\}\_\{u\\in\\\{0,1\\\}^\{r\}\}\\widehat\{p\}\_\{u\}\.The empirical risk minimizer overℱr\\mathcal\{F\}^\{r\}is the constant hypothesishu^h\_\{\\widehat\{u\}\}\.

###### Proposition 1\.

For alln,r≥1n,r\\geq 1,

εagn​\(n∣ℱr\)≍1n,\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{F\}^\{r\}\)\\asymp\\frac\{1\}\{\\sqrt\{n\}\},where the implicit constants are universal\.

###### Proof\.

SinceLD​\(hu\)=1−puL\_\{D\}\(h\_\{u\}\)=1\-p\_\{u\},

LD​\(hu^\)−LD​\(ℱr\)=pu⋆−pu^\.L\_\{D\}\(h\_\{\\widehat\{u\}\}\)\-L\_\{D\}\(\\mathcal\{F\}^\{r\}\)=p\_\{u^\{\\star\}\}\-p\_\{\\widehat\{u\}\}\.The definition ofu^\\widehat\{u\}gives

pu⋆−pu^\\displaystyle p\_\{u^\{\\star\}\}\-p\_\{\\widehat\{u\}\}≤\(pu⋆−p^u⋆\)\+\(p^u^−pu^\)\\displaystyle\\leq\(p\_\{u^\{\\star\}\}\-\\widehat\{p\}\_\{u^\{\\star\}\}\)\+\(\\widehat\{p\}\_\{\\widehat\{u\}\}\-p\_\{\\widehat\{u\}\}\)≤2​‖p^−p‖∞≤2​‖p^−p‖2\.\\displaystyle\\leq 2\\\|\\widehat\{p\}\-p\\\|\_\{\\infty\}\\leq 2\\\|\\widehat\{p\}\-p\\\|\_\{2\}\.Consequently, by Jensen’s inequality,

𝔼​\[pu⋆−pu^\]\\displaystyle\\mathbb\{E\}\\bigl\[p\_\{u^\{\\star\}\}\-p\_\{\\widehat\{u\}\}\\bigr\]≤2​𝔼​‖p^−p‖22\\displaystyle\\leq 2\\sqrt\{\\mathbb\{E\}\\\|\\widehat\{p\}\-p\\\|\_\{2\}^\{2\}\}=2​∑uVar⁡\(p^u\)\\displaystyle=2\\sqrt\{\\sum\_\{u\}\\operatorname\{Var\}\(\\widehat\{p\}\_\{u\}\)\}=2​1−∑upu2n≤2n\.\\displaystyle=2\\sqrt\{\\frac\{1\-\\sum\_\{u\}p\_\{u\}^\{2\}\}\{n\}\}\\leq\\frac\{2\}\{\\sqrt\{n\}\}\.This proves the upper bound uniformly overDDandrr\.

For the lower bound, fix an inputx0∈𝒳rx\_\{0\}\\in\\mathcal\{X\}^\{r\}and restrict the label distribution to0r0^\{r\}and1r1^\{r\}, with probabilities1/2\+α1/2\+\\alphaand1/2−α1/2\-\\alpha\. Distinguishing which label is more likely is the standard two\-point Bernoulli problem\. Le Cam’s method withα\\alphaof ordern−1/2n^\{\-1/2\}gives an expected excess risk of ordern−1/2n^\{\-1/2\}; see\[[TSY09](https://arxiv.org/html/2608.06951#bib.bib9), Chapter 2\]\. ∎

### 3\.2Direct sums of the zero and identity functions

Forb=\(b1,…,br\)∈\{0,1\}rb=\(b\_\{1\},\\ldots,b\_\{r\}\)\\in\\\{0,1\\\}^\{r\}, write

hb=gb1⊗⋯⊗gbr∈𝒢r\.h\_\{b\}=g\_\{b\_\{1\}\}\\otimes\\cdots\\otimes g\_\{b\_\{r\}\}\\in\\mathcal\{G\}^\{r\}\.Becausegb​\(x\)=b​xg\_\{b\}\(x\)=bx,

hb​\(x1,…,xr\)=\(b1​x1,…,br​xr\)\.h\_\{b\}\(x\_\{1\},\\ldots,x\_\{r\}\)=\(b\_\{1\}x\_\{1\},\\ldots,b\_\{r\}x\_\{r\}\)\.\(9\)Leteje\_\{j\}be thejjth standard basis vector in\{0,1\}r\\\{0,1\\\}^\{r\}\. Then

hb​\(ej\)=\{0r,bj=0,ej,bj=1\.h\_\{b\}\(e\_\{j\}\)=\\begin\{cases\}0^\{r\},&b\_\{j\}=0,\\\\ e\_\{j\},&b\_\{j\}=1\.\\end\{cases\}\(10\)
The upper bound in \([7](https://arxiv.org/html/2608.06951#S3.E7)\) follows from the finite\-class estimate\. Since\|𝒢r\|=2r\|\\mathcal\{G\}^\{r\}\|=2^\{r\}, equation \([3](https://arxiv.org/html/2608.06951#S2.E3)\) gives

εagn​\(n∣𝒢r\)≤K​min⁡\{1,r​log⁡2n\}\.\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid\\mathcal\{G\}^\{r\}\)\\leq K\\min\\left\\\{1,\\sqrt\{\\frac\{r\\log 2\}\{n\}\}\\right\\\}\.\(11\)
For the lower bound, fix a learning ruleAAand a number0<α≤1/40<\\alpha\\leq 1/4\. For everyθ=\(θ1,…,θr\)∈\{−1,\+1\}r\\theta=\(\\theta\_\{1\},\\ldots,\\theta\_\{r\}\)\\in\\\{\-1,\+1\\\}^\{r\}, define a distributionDθD\_\{\\theta\}on𝒳r×𝒴r\\mathcal\{X\}^\{r\}\\times\\mathcal\{Y\}^\{r\}as follows\. ChooseJJuniformly from\{1,…,r\}\\\{1,\\ldots,r\\\}, setX=eJX=e\_\{J\}, and, conditional onJ=jJ=j, set

Y=\{ej,with probability​12\+θj​α,0r,with probability​12−θj​α\.Y=\\begin\{cases\}e\_\{j\},&\\text\{with probability \}\\frac\{1\}\{2\}\+\\theta\_\{j\}\\alpha,\\\\ 0^\{r\},&\\text\{with probability \}\\frac\{1\}\{2\}\-\\theta\_\{j\}\\alpha\.\\end\{cases\}\(12\)For a fixedjj, the more likely label ateje\_\{j\}iseje\_\{j\}whenθj=\+1\\theta\_\{j\}=\+1and0r0^\{r\}whenθj=−1\\theta\_\{j\}=\-1\. Define

bj⋆​\(θ\)=1\+θj2\.b\_\{j\}^\{\\star\}\(\\theta\)=\\frac\{1\+\\theta\_\{j\}\}\{2\}\.By \([10](https://arxiv.org/html/2608.06951#S3.E10)\),hb⋆​\(θ\)h\_\{b^\{\\star\}\(\\theta\)\}predicts the more likely label at everyeje\_\{j\}\. Therefore

LDθ​\(𝒢r\)=12−α\.L\_\{D\_\{\\theta\}\}\(\\mathcal\{G\}^\{r\}\)=\\frac\{1\}\{2\}\-\\alpha\.\(13\)
LetS∼DθnS\\sim D\_\{\\theta\}^\{n\}\. From the output ofAAdefineθ^A​\(S\)∈\{−1,\+1\}r\\widehat\{\\theta\}\_\{A\}\(S\)\\in\\\{\-1,\+1\\\}^\{r\}by

θ^A,j​\(S\)=\{\+1,A​\(S\)​\(ej\)=ej,−1,A​\(S\)​\(ej\)≠ej\.\\widehat\{\\theta\}\_\{A,j\}\(S\)=\\begin\{cases\}\+1,&A\(S\)\(e\_\{j\}\)=e\_\{j\},\\\\ \-1,&A\(S\)\(e\_\{j\}\)\\neq e\_\{j\}\.\\end\{cases\}\(14\)We now relate errors inθ^A\\widehat\{\\theta\}\_\{A\}to excess risk\. Fixjj\. Ifθj=\+1\\theta\_\{j\}=\+1butθ^A,j=−1\\widehat\{\\theta\}\_\{A,j\}=\-1, then the learner does not predict the more likely labeleje\_\{j\}\. Predicting0r0^\{r\}has conditional error1/2\+α1/2\+\\alpha, and any other prediction has conditional error one\. Ifθj=−1\\theta\_\{j\}=\-1butθ^A,j=\+1\\widehat\{\\theta\}\_\{A,j\}=\+1, then the learner predictseje\_\{j\}although0r0^\{r\}is more likely, and its conditional error is1/2\+α1/2\+\\alpha\. In either case, the conditional excess over the optimal error1/2−α1/2\-\\alphais at least2​α2\\alpha\. SinceX=ejX=e\_\{j\}with probability1/r1/r, each incorrect coordinate contributes at least2​α/r2\\alpha/rto the population excess risk\. Hence, for everyθ\\thetaand every sampleSS,

LDθ​\(A​\(S\)\)−LDθ​\(𝒢r\)≥2​αr​dH​\(θ^A​\(S\),θ\)\.L\_\{D\_\{\\theta\}\}\(A\(S\)\)\-L\_\{D\_\{\\theta\}\}\(\\mathcal\{G\}^\{r\}\)\\geq\\frac\{2\\alpha\}\{r\}\\,d\_\{\\mathrm\{H\}\}\\bigl\(\\widehat\{\\theta\}\_\{A\}\(S\),\\theta\\bigr\)\.\(15\)This inequality also covers improper learning rules, since predictions outside\{0r,ej\}\\\{0^\{r\},e\_\{j\}\\\}have conditional error one\.

It remains to bound the accuracy with whichθ\\thetacan be estimated\. Letθ\(j\)\\theta^\{\(j\)\}be obtained by changing only the sign ofθj\\theta\_\{j\}\. The distributionsDθD\_\{\\theta\}andDθ\(j\)D\_\{\\theta^\{\(j\)\}\}agree unlessX=ejX=e\_\{j\}, an event of probability1/r1/r\. Conditional on this event, the probability of the labeleje\_\{j\}changes from1/2\+α1/2\+\\alphato1/2−α1/2\-\\alpha, or conversely\. Therefore

KL⁡\(Dθ∥Dθ\(j\)\)\\displaystyle\\operatorname\{KL\}\(D\_\{\\theta\}\\\|D\_\{\\theta^\{\(j\)\}\}\)=1r​KL⁡\(Ber⁡\(12\+α\)∥Ber⁡\(12−α\)\)\\displaystyle=\\frac\{1\}\{r\}\\,\\operatorname\{KL\}\\left\(\\operatorname\{Ber\}\\left\(\\frac\{1\}\{2\}\+\\alpha\\right\)\\middle\\\|\\operatorname\{Ber\}\\left\(\\frac\{1\}\{2\}\-\\alpha\\right\)\\right\)=2​αr​log⁡\(1\+2​α1−2​α\)≤16​α2r\.\\displaystyle=\\frac\{2\\alpha\}\{r\}\\log\\left\(\\frac\{1\+2\\alpha\}\{1\-2\\alpha\}\\right\)\\leq\\frac\{16\\alpha^\{2\}\}\{r\}\.\(16\)By independence,

KL⁡\(Dθn∥Dθ\(j\)n\)≤16​n​α2r\.\\operatorname\{KL\}\(D\_\{\\theta\}^\{n\}\\\|D\_\{\\theta^\{\(j\)\}\}^\{n\}\)\\leq\\frac\{16n\\alpha^\{2\}\}\{r\}\.\(17\)Choose

α=116​min⁡\{1,rn\}\.\\alpha=\\frac\{1\}\{16\}\\min\\left\\\{1,\\sqrt\{\\frac\{r\}\{n\}\}\\right\\\}\.\(18\)Then the right\-hand side of \([17](https://arxiv.org/html/2608.06951#S3.E17)\) is at most1/161/16\. Pinsker’s inequality gives

TV⁡\(Dθn,Dθ\(j\)n\)≤132<14\\operatorname\{TV\}\(D\_\{\\theta\}^\{n\},D\_\{\\theta^\{\(j\)\}\}^\{n\}\)\\leq\\sqrt\{\\frac\{1\}\{32\}\}<\\frac\{1\}\{4\}\(19\)for everyθ\\thetaandjj\. Applying Assouad’s lemma to the family\{Dθn\}\\\{D\_\{\\theta\}^\{n\}\\\},

supθ∈\{−1,\+1\}r𝔼S∼Dθn​\[dH​\(θ^A​\(S\),θ\)\]≥3​r8\.\\sup\_\{\\theta\\in\\\{\-1,\+1\\\}^\{r\}\}\\mathbb\{E\}\_\{S\\sim D\_\{\\theta\}^\{n\}\}\\bigl\[d\_\{\\mathrm\{H\}\}\(\\widehat\{\\theta\}\_\{A\}\(S\),\\theta\)\\bigr\]\\geq\\frac\{3r\}\{8\}\.\(20\)Combining \([15](https://arxiv.org/html/2608.06951#S3.E15)\) and \([20](https://arxiv.org/html/2608.06951#S3.E20)\),

supD\(LD,n​\(A\)−LD​\(𝒢r\)\)\\displaystyle\\sup\_\{D\}\\bigl\(L\_\{D,n\}\(A\)\-L\_\{D\}\(\\mathcal\{G\}^\{r\}\)\\bigr\)≥supθ∈\{−1,\+1\}r𝔼S∼Dθn​\[LDθ​\(A​\(S\)\)−LDθ​\(𝒢r\)\]\\displaystyle\\geq\\sup\_\{\\theta\\in\\\{\-1,\+1\\\}^\{r\}\}\\mathbb\{E\}\_\{S\\sim D\_\{\\theta\}^\{n\}\}\\bigl\[L\_\{D\_\{\\theta\}\}\(A\(S\)\)\-L\_\{D\_\{\\theta\}\}\(\\mathcal\{G\}^\{r\}\)\\bigr\]≥2​αr⋅3​r8=3​α4\.\\displaystyle\\geq\\frac\{2\\alpha\}\{r\}\\cdot\\frac\{3r\}\{8\}=\\frac\{3\\alpha\}\{4\}\.SinceAAwas arbitrary, taking the infimum overAAand substituting \([18](https://arxiv.org/html/2608.06951#S3.E18)\) proves the lower bound in \([7](https://arxiv.org/html/2608.06951#S3.E7)\)\. Together with \([11](https://arxiv.org/html/2608.06951#S3.E11)\), this proves \([7](https://arxiv.org/html/2608.06951#S3.E7)\) and completes the proof of Theorem[1](https://arxiv.org/html/2608.06951#Thmtheorem1)\.

## 4Conclusion

The classesℱ\\mathcal\{F\}and𝒢\\mathcal\{G\}have the same single\-instance agnostic learning rate, but their direct sums do not\. When1≤r≤n1\\leq r\\leq n, the rate for𝒢r\\mathcal\{G\}^\{r\}is larger than the rate forℱr\\mathcal\{F\}^\{r\}by a factor of orderr\\sqrt\{r\}\. Whenr≥nr\\geq n, the minimax excess risk for𝒢r\\mathcal\{G\}^\{r\}is bounded below by a positive constant, while the rate forℱr\\mathcal\{F\}^\{r\}remains of ordern−1/2n^\{\-1/2\}\. Therefore the asymptotic order ofεagn​\(n∣C\)\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C\)and the value ofrrare not sufficient to determine the asymptotic order ofεagn​\(n∣Cr\)\\varepsilon\_\{\\mathrm\{agn\}\}\(n\\mid C^\{r\}\)for an arbitrary concept classCC\.

## References

- \[ASS83\]P\. Assouad\(1983\)Deux remarques sur l’estimation\.Comptes Rendus de l’Académie des Sciences\. Série I\. Mathématique296\(23\),pp\. 1021–1024\.Cited by:[Lemma 1](https://arxiv.org/html/2608.06951#Thmlemma1)\.
- \[CEH\+25\]A\. Cohen, L\. Erez, S\. Hanneke, T\. Koren, Y\. Mansour, S\. Moran, and Q\. Zhang\(2025\)Sample complexity of agnostic multiclass classification: natarajan dimension strikes back\.arXiv preprint arXiv:2511\.12659\.External Links:2511\.12659Cited by:[§1](https://arxiv.org/html/2608.06951#S1.p2.3)\.
- \[DGL96\]L\. Devroye, L\. Györfi, and G\. Lugosi\(1996\)A probabilistic theory of pattern recognition\.Springer,New York\.External Links:[Document](https://dx.doi.org/10.1007/978-1-4612-0711-5)Cited by:[§2](https://arxiv.org/html/2608.06951#S2.p5.6)\.
- \[HMW24\]S\. Hanneke, S\. Moran, and T\. Waknine\(2024\)Open problem: direct sums in learning theory\.InProceedings of the 37th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.247,pp\. 5325–5329\.External Links:[Link](https://proceedings.mlr.press/v247/hanneke24c.html)Cited by:[§1](https://arxiv.org/html/2608.06951#S1.p1.3),[§1](https://arxiv.org/html/2608.06951#S1.p2.3),[§2](https://arxiv.org/html/2608.06951#S2.p1.3),[§2](https://arxiv.org/html/2608.06951#S2.p2.8)\.
- \[HMS26\]R\. Holzman, S\. Moran, and A\. Shlimovich\(2026\)Uniform laws of large numbers in product spaces\.InProceedings of the 39th Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.336,pp\. 3224–3279\.External Links:[Link](https://proceedings.mlr.press/v336/holzman26a.html)Cited by:[§1](https://arxiv.org/html/2608.06951#S1.p2.3)\.
- \[PAB26\]C\. Pabbaraju\(2026\)The optimal sample complexity of multiclass and list learning\.arXiv preprint arXiv:2604\.24749\.External Links:2604\.24749Cited by:[§1](https://arxiv.org/html/2608.06951#S1.p2.3)\.
- \[SUR24\]D\. Suruga\(2024\)Direct sum theorems beyond query complexity\.arXiv preprint arXiv:2408\.15570\.External Links:2408\.15570Cited by:[§1](https://arxiv.org/html/2608.06951#S1.p2.3)\.
- \[TSY09\]A\. B\. Tsybakov\(2009\)Introduction to nonparametric estimation\.Springer Series in Statistics,Springer,New York\.External Links:[Document](https://dx.doi.org/10.1007/b13794)Cited by:[§2](https://arxiv.org/html/2608.06951#S2.p5.11),[§3\.1](https://arxiv.org/html/2608.06951#S3.SS1.2.p2.8),[Lemma 1](https://arxiv.org/html/2608.06951#Thmlemma1)\.