Minimax learning lower bounds and optimal rates

For any randomized test, its average error is at least $(1-\mathrm{TV}(P_{-}^k,P_{+}^k))\mathrm{/}2$: writing the two error expectations over the common finite sample space gives $e_k(\psi )=\frac{1}{2}(1-{\sum }_{\omega }\psi (\omega )(P_{+}^k(\omega )-P_{-}^k(\omega )))$. Each $\psi (\omega )\in [0,1]$ makes the signed sum at most the sum of the positive differences; these differences sum to $\frac{1}{2}{\sum }_{\omega }\mathrm{\mid }{P}_{+}^k(\omega )-P_{-}^k(\omega )\mathrm{\mid }$ because their total signed sum is zero. This is $\mathrm{TV}(P_{-}^k,P_{+}^k)$ by the definition in the statement.

For any finite laws $Q,R$, write $\mathrm{\mid }Q(\omega )-R(\omega )\mathrm{\mid }=\mathrm{\mid }\sqrt{Q}-\sqrt{R}\mathrm{\mid }(\sqrt{Q}+\sqrt{R})$. The finite Cauchy–Schwarz inequality follows by expanding ${\sum }_i(a_i-\lambda b_i{)}^2\ge 0$ with $\lambda =({\sum }_i{a}_i{b}_i)\mathrm{/}({\sum }_i{b}_i^2)$ when the denominator is positive, and is immediate when it is zero. Apply it to $a_{\omega }=\mathrm{\mid }\sqrt{Q(\omega )}-\sqrt{R(\omega )}\mathrm{\mid }$ and $b_{\omega }=\sqrt{Q(\omega )}+\sqrt{R(\omega )}$ to obtain $\mathrm{TV}(Q,R{)}^2\le \frac{1}{4}({\sum }_{\omega }(\sqrt{Q}-\sqrt{R}{)}^2)({\sum }_{\omega }(\sqrt{Q}+\sqrt{R}{)}^2)=1-\mathrm{aff}(Q,R{)}^2$. Thus $e_k(\psi )\ge \frac{1}{2}(1-\sqrt{1-\mathrm{aff}(P_{-}^k,P_{+}^k{)}^2})$.

The single-observation affinity is $2\sqrt{(1-u^2)\mathrm{/}4}=\sqrt{1-u^2}$. Finite product distributivity makes the $k$-observation affinity its $k$th power, $(1-u^2{)}^{k\mathrm{/}2}$; substituting gives the first displayed lower bound.

For $0\le x<1$, $g(x)=\log (1-x)+x\mathrm{/}(1-x)$ satisfies $g(0)=0$ and $g^{\mathrm{\prime }}(x)=x\mathrm{/}(1-x{)}^2\ge 0$, so $(1-u^2{)}^k\ge \exp (-k{u}^2\mathrm{/}(1-u^2))$. Since $2\lceil k\mathrm{/}2\rceil \ge k$, the exponential with exponent $-k{u}^2\mathrm{/}(1-u^2)$ is at least the one with exponent $-2\lceil k\mathrm{/}2\rceil u^2\mathrm{/}(1-u^2)$. The map $s\mapsto 1-\sqrt{1-s}$ is increasing on $[0,1]$, so the first lower bound is at least $2\mathrm{\Phi }(2\lceil k\mathrm{/}2\rceil ,u)$.

With no observations the test's decision distribution is the same under both signs, so its equal-prior error is $\frac{1}{2}(q+(1-q))=\frac{1}{2}$ for its probability $q$ of deciding $+$.

Splitting the expectation on $\{Z\le t\}$ and $\{Z>t\}$ and using $Z\le t$ on the first event and $Z\le 1$ on the second gives $\mathbb{E}Z\le t\mathrm{Pr}\{Z\le t\}+\mathrm{Pr}\{Z>t\}=t+(1-t)\mathrm{Pr}\{Z>t\}$.

Since $1-t>0$, rearranging the inequality in step 1.1 gives $\mathrm{Pr}\{Z>t\}\ge (\mathbb{E}Z-t)\mathrm{/}(1-t)$.

Since $d$ is the finite VC dimension, choose distinct $x_0,x_1,\dots ,x_{d-1}$ shattered by $\mathcal{H}$. For each of the finitely many label vectors $\theta \in \{0,1{\}}^d$, shattering supplies a target $f_{\theta }\in \mathcal{H}$ with those labels on these points; finite choice suffices for this finite family. Put $ϵ=(d-1)\mathrm{/}(32m)$ and define the finite mixture $\mu =(1-8ϵ){\delta }_{x_0}+{\sum }_{i=1}^{d-1}\frac{8ϵ}{d-1}{\delta }_{x_i}$. The range on $m$ gives $8ϵ=(d-1)\mathrm{/}(4m)\le 1$, so all mixture weights are nonnegative and sum to one. For each $\theta$, let $D_{\theta }$ be the law of $(X,f_{\theta }(X))$ for $X\sim \mu$.

Let $M$ count sample positions drawn from the rare atoms $x_1,\dots ,x_{d-1}$. Then $M\sim \mathrm{Bin}(m,8ϵ)$ and ${\mu }_0:=\mathbb{E}M=(d-1)\mathrm{/}4\ge 1\mathrm{/}4$. Since $e^p={\sum }_{j=0}^{\mathrm{\infty }}{p}^j\mathrm{/}j!\ge 1+p$ for $p\ge 0$, $\mathbb{E}{2}^M=(1+8ϵ{)}^m\le e^{{\mu }_0}$. For any nonnegative random variable $X$ and $b>0$, $\mathbb{E}X\ge b\mathrm{Pr}\{X\ge b\}$ because $X\ge b{\mathbf{1}}_{\{X\ge b\}}$; apply this to $X=2^M$ and $b=2^{2{\mu }_0}$. On $\{M\ge 2{\mu }_0\}$, $2^M\ge 2^{2{\mu }_0}$, hence $\mathrm{Pr}\{M\ge 2{\mu }_0\}\le e^{{\mu }_0-2{\mu }_0\log 2}\le e^{-{\mu }_0\mathrm{/}3}$, where $\log 2\ge 2\mathrm{/}3$ because $g(x)=\log x-2(x-1)\mathrm{/}(x+1)$ has $g(1)=0$ and $g^{\mathrm{\prime }}(x)=(x-1{)}^2\mathrm{/}(x(x+1{)}^2)\ge 0$ for $x\ge 1$. Since $2{\mu }_0=(d-1)\mathrm{/}2$, $\mathrm{Pr}\{M\le (d-1)\mathrm{/}2\}\ge 1-e^{-{\mu }_0\mathrm{/}3}\ge 1-e^{-1\mathrm{/}12}\ge 1\mathrm{/}13$; the last inequality follows from $e^{1\mathrm{/}12}\ge 1+1\mathrm{/}12=13\mathrm{/}12$.

Fix any vector of sample atom indices and observed labels for which $M\le (d-1)\mathrm{/}2$. At least $(d-1)\mathrm{/}2$ rare atoms were not observed. Under the uniform prior on $\theta$, each unseen label ${\theta }_i$ is still an independent fair bit, independent of the learner's output at $x_i$, because the learner depends only on the observed sample and independent internal randomness. Therefore, if $W$ is the learner's risk contribution from $x_1,\dots ,x_{d-1}$, then ${\mathbb{E}}_{\theta ,A}[W\mid \text{observed data}]\ge \frac{1}{2}\frac{d-1}{2}\frac{8ϵ}{d-1}=2ϵ$, while $0\le W\le 8ϵ$. Applying [F2] to $W\mathrm{/}(8ϵ)$ at $t=1\mathrm{/}8$ yields ${\mathrm{Pr}}_{\theta ,A}\{W>ϵ\mid \text{observed data}\}\ge 1\mathrm{/}7$.

Each $D_{\theta }$ is realizable by $f_{\theta }$, so [F4] gives $R_{D_{\theta }}^{\ast }(\mathcal{H})=0$. By [F3] and the event $Y=f_{\theta }(X)$ of probability one, the zero-one risk and target risk of the learner's output agree. The full target risk is at least $W$. Averaging step 1.3 over sample locations and labels, then using step 1.2, gives ${\mathrm{Pr}}_{\theta ,S\sim D_{\theta }^m,A}\{R_{D_{\theta }}(A(S),f_{\theta })>ϵ\}\ge \frac{1}{7}\cdot \frac{1}{13}=\frac{1}{91}>\frac{1}{100}$. This is an average over the finite set $\{0,1{\}}^d$, so at least one $\theta$ has conditional failure probability at least $1\mathrm{/}91$. Its $D_{\theta }$ and $f_{\theta }$ satisfy the statement.

Put $r=\sqrt{d\mathrm{/}(320m)}$ and $a=64r\mathrm{/}7$. The sample range gives $r\le 1\mathrm{/}64$ and $0<a\le 1\mathrm{/}7$. Choose distinct $x_1,\dots ,x_d$ shattered by $\mathcal{H}$. For each $\sigma \in \{-1,+1{\}}^d$, define $D_{\sigma }:=\frac{1}{d}{\sum }_{i=1}^d[(\frac{1}{2}+\frac{{\sigma }_{i}a}{2}){\delta }_{(x_i,1)}+(\frac{1}{2}-\frac{{\sigma }_{i}a}{2}){\delta }_{(x_i,0)}]$. The weights are nonnegative and sum to one, so [A1] makes this a probability law. The Bayes label $b_i={\mathbf{1}}_{\{{\sigma }_i=+1\}}$ is realized on these points by some $h\in \mathcal{H}$ by [F1]. At atom $x_i$, predicting $b_i$ has error $(1-a)\mathrm{/}2$, while predicting $1-b_i$ has error $(1+a)\mathrm{/}2$, by the two point masses in $D_{\sigma }$. Since each atom has marginal weight $1\mathrm{/}d$, the class benchmark is $(1-a)\mathrm{/}2$ and every binary predictor $g$ has excess risk $R_{D_{\sigma }}(g)-{\inf }_{h\in \mathcal{H}}{R}_{D_{\sigma }}(h)=\frac{a}{d}{\sum }_{i=1}^d{\mathbf{1}}_{\{g(x_i)\mathrm{\ne }{b}_i\}}$. This identity holds for every binary output $g$.

For $c=a^2\mathrm{/}(1-a^2)>0$ and $q=e^{-ct}$, direct differentiation of $\mathrm{\Phi }(t,a)=\frac{1}{4}(1-\sqrt{1-q})$ gives ${\mathrm{\Phi }}^{\mathrm{\prime }}(t,a)=-\frac{cq}{8\sqrt{1-q}}<0$ and ${\mathrm{\Phi }}^{\mathrm{\prime }\mathrm{\prime }}(t,a)=\frac{c^{2}q(2-q)}{16(1-q{)}^{3\mathrm{/}2}}>0$ for $t>0$. Also $\mathrm{\Phi }(0,a)=1\mathrm{/}4$ and $\mathrm{\Phi }$ is continuous there. Approximating any zero endpoint in the monotonicity and convexity inequalities by positive arguments and taking limits extends both properties to $[0,\mathrm{\infty })$.

Fix coordinate $i$ and condition on all other signs and all sample data outside $x_i$. Given $N_i=k\ge 1$ observations at $x_i$, the learner's prediction there is a randomized test of ${\sigma }_i$ based on $k$ iid labels with the two laws in [F2]. Its conditional average mistake probability is at least $2\mathrm{\Phi }(2\lceil k\mathrm{/}2\rceil ,a)$. Since $2\lceil k\mathrm{/}2\rceil \le k+1$ and $\mathrm{\Phi }$ is decreasing by step 1.2, this is at least $2\mathrm{\Phi }(k+1,a)>\mathrm{\Phi }(k+1,a)$. For $k=0$ the prediction is independent of ${\sigma }_i$, so its average mistake probability is $1\mathrm{/}2>\mathrm{\Phi }(1,a)$ because $0<\mathrm{\Phi }(1,a)<1\mathrm{/}4$.

Put $s=d\mathrm{/}m\le 5\mathrm{/}64$. Since $a^2=64s\mathrm{/}245$ and $m\mathrm{/}d=1\mathrm{/}s$, $c(m\mathrm{/}d+1)=\frac{64}{245}\frac{1+s}{1-(64\mathrm{/}245)s}\le \frac{23}{80}$. The derivative of $h(s)=\frac{64}{245}\frac{1+s}{1-(64\mathrm{/}245)s}$ is $\frac{(64\mathrm{/}245)(1+64\mathrm{/}245)}{(1-(64\mathrm{/}245)s{)}^2}>0$, and direct substitution gives $h(5\mathrm{/}64)=23\mathrm{/}80$. Moreover, $\ln (4\mathrm{/}3)={\int }_0^{1\mathrm{/}3}\frac{dx}{1+x}>\frac{1}{3}-\frac{1}{18}+\frac{1}{81}-\frac{1}{324}+\frac{1}{1215}-\frac{1}{4374}=\frac{12581}{43740}>\frac{23}{80}$. The strict lower bound follows from $1\mathrm{/}(1+x)=1-x+x^2-x^3+x^4-x^5+x^6\mathrm{/}(1+x)$, whose remainder is positive on $(0,1\mathrm{/}3]$; the final rational comparison follows from $80\cdot 12581=1006480>1006020=23\cdot 43740$. Hence $c(m\mathrm{/}d+1)<\ln (4\mathrm{/}3)$, so $e^{-c(m\mathrm{/}d+1)}>3\mathrm{/}4$ and therefore $\mathrm{\Phi }(m\mathrm{/}d+1,a)>1\mathrm{/}8$.

Let $N_i$ count occurrences of $x_i$; $N_i\sim \mathrm{Bin}(m,1\mathrm{/}d)$, so $\mathbb{E}(N_i+1)=m\mathrm{/}d+1=:t_0>0$. With $Z$ equal to the excess risk in step 1.1 divided by $a$, we have $Z\in [0,1]$. Averaging the strict coordinate bounds of step 2.1 over the finitely many coordinates, sample counts, signs, and learner randomization gives $\mathbb{E}Z>\mathbb{E}\mathrm{\Phi }(N_i+1,a)$. By step 1.2, ${\mathrm{\Phi }}^{\mathrm{\prime }}$ is increasing on $(0,\mathrm{\infty })$. For each possible value $x=N_i+1>0$, if $x>t_0$ the mean value theorem gives $\mathrm{\Phi }(x,a)-\mathrm{\Phi }(t_0,a)={\mathrm{\Phi }}^{\mathrm{\prime }}(\xi ,a)(x-t_0)\ge {\mathrm{\Phi }}^{\mathrm{\prime }}(t_0,a)(x-t_0)$ for some $\xi \in (t_0,x)$; if $x<t_0$, it gives the same inequality because ${\mathrm{\Phi }}^{\mathrm{\prime }}(\xi ,a)\le {\mathrm{\Phi }}^{\mathrm{\prime }}(t_0,a)$ for some $\xi \in (x,t_0)$ and $x-t_0<0$; equality holds when $x=t_0$. Summing this finite inequality over the distribution of $N_i$ cancels the linear term because $\mathbb{E}(N_i+1)=t_0$, so $\mathbb{E}\mathrm{\Phi }(N_i+1,a)\ge \mathrm{\Phi }(t_0,a)=:v$. Therefore $\mathbb{E}Z>v$.

The prior on $\sigma$ is finite. Since the joint average in step 3.1 is greater than $v>1\mathrm{/}8$, some $\sigma$ has ${\mathbb{E}}_{S\sim D_{\sigma }^m,A}Z>1\mathrm{/}8$.

For this $\sigma$, $r\mathrm{/}a=7\mathrm{/}64$. Apply [F3] to $Z$ at $t=7\mathrm{/}64$: $\mathrm{Pr}\{Z>7\mathrm{/}64\}\ge \frac{\mathbb{E}Z-7\mathrm{/}64}{57\mathrm{/}64}>\frac{1\mathrm{/}8-7\mathrm{/}64}{57\mathrm{/}64}=\frac{1}{57}>\frac{1}{64}$. Since $a(7\mathrm{/}64)=r$, the event is exactly that the class excess risk exceeds $r$.

For a nonnegative random variable $X$ and $t\ge 0$, $X\ge t{\mathbf{1}}_{\{X>t\}}$ pointwise, so $\mathbb{E}X\ge t\mathrm{Pr}\{X>t\}$. For each learner, [F1] supplies a realizable law with target risk exceeding $(d-1)\mathrm{/}(32m)$ with probability at least $1\mathrm{/}100$; since the supremum over realizable laws is at least this expectation, [F3] gives ${\mathfrak{M}}_{\mathrm{r}\mathrm{e}\mathrm{a}\mathrm{l}}\ge \frac{1}{100}\frac{d-1}{32m}=\frac{d-1}{3200m}\ge \frac{d}{6400m}$ because $d-1\ge d\mathrm{/}2$. Likewise [F2], nonnegativity in [F5], and the supremum over all laws in [F4] give ${\mathfrak{M}}_{\mathrm{a}\mathrm{g}\mathrm{n}}\ge \frac{1}{64}\sqrt{d\mathrm{/}(320m)}$.

If $m<(d-1)\mathrm{/}(32\eta )$ then $(d-1)\mathrm{/}(32m)>\eta$, so the event in [F1] is contained in the event of error exceeding $\eta$. Its probability is at least $1\mathrm{/}100>\delta$. If $m<d\mathrm{/}(320{\eta }^2)$ then $\sqrt{d\mathrm{/}(320m)}>\eta$, so [F2] similarly gives failure probability at least $1\mathrm{/}64>\delta$. Thus any successful sample size in the respective theorem range must be at least $(d-1)\mathrm{/}(32\eta )$ or $d\mathrm{/}(320{\eta }^2)$, respectively. Since $d-1\ge d\mathrm{/}2$ for $d\ge 2$, the first is at least $d\mathrm{/}(64\eta )$; the second is already a constant multiple of $d\mathrm{/}{\eta }^2$.