The Minimax Rate of Online Isotonic Regression on Product Orders

(a). By the closed form in Lemma 10 and the continuity of $A$ on $[0,\infty)$ (with $A(0)=0$), $\varphi$ is continuous on $[0,\infty)\text{.}$ Substituting $\alpha=0$ yields $\varphi(0)=A(2)-2A(1)+A(0)-2\log 2=0\text{.}$

(b), (c). By the integral representation, for $\alpha>0$ differentiation under the integral sign is legitimate (on any compact sub-interval $[\alpha_{0},\alpha_{1}]\subset(0,\infty)\text{,}$ the integrand and its $\alpha$-partial derivative are uniformly dominated by an integrable function):

Hence $\varphi$ is strictly increasing and strictly concave on $(0,\infty)\text{;}$ continuity extends both properties to $[0,\infty)\text{.}$ As $\alpha\downarrow 0$ the integrand $(\alpha+s+t)^{-1}$ increases pointwise to $(s+t)^{-1}\text{,}$ so by monotone convergence

whence $\varphi^{\prime}$ extends continuously to $[0,\infty)$ with $\varphi^{\prime}(0)=2\log 2\text{;}$ since $\varphi$ is continuous at $0\text{,}$ the mean value theorem identifies this limit with the right derivative of $\varphi$ there.

(d). Since $\log(1+x)\leq x$ for $x\geq 0\text{,}$

(e). Define $g(\alpha):=\log\alpha+2-\varphi(\alpha)$ for $\alpha>0\text{.}$ Then $g^{\prime}(\alpha)=1/\alpha-\varphi^{\prime}(\alpha)\text{.}$ Since $s+t>0$ almost everywhere on $(0,1]^{2}\text{,}$

so $g^{\prime}(\alpha)>0$ and $g$ is strictly increasing on $(0,\infty)\text{.}$ At $\alpha=1/2\text{,}$ part (d) gives $\varphi(1/2)\leq 2(\log 2)(1/2)=\log 2\text{,}$ hence

Since $g$ is increasing, $g(\alpha)\geq g(1/2)>0$ for all $\alpha\geq 1/2\text{.}$

(f). Since $s+t\leq 2$ on $[0,1]^{2}\text{,}$ the integrand obeys $\log(1+\alpha/(s+t))\geq\log(1+\alpha/2)$ pointwise, so

which diverges as $\alpha\to\infty\text{.}$ ∎

The proof proceeds in three steps; throughout, abbreviate $\log\Omega:=\log\Omega([m]^{2},K{+}1)=H_{[m]^{2}}(K)\text{.}$

Step 1 (Barnes $G$ representation). By Theorem 4,

where the inner sum over $j$ telescopes via $\sum_{j=1}^{m}\log(N+j)=\log\Gamma(N+m+1)-\log\Gamma(N+1)\text{.}$ Define

By Fact 12, $\log G(n+1)=\sum_{j=1}^{n}\log\Gamma(j)$ for every positive integer $n\text{,}$ so

Since $\log\Omega=[S(K+m)-S(K)]-[S(m)-S(0)]\text{,}$ expanding (19) gives

Subtracting,

Step 2 (Apply Barnes $G$ asymptotic). Apply the asymptotic expansion (17) of Fact 12 to each term $\log G(z_{i}+1)$ in (20), where

with coefficients $c:=(+1,-2,+1,-1,+2)\text{.}$ Aggregating term by term:

Step 3 ($\sum_{i}c_{i}A(z_{i})=m^{2}\,\varphi(K/m)\text{:}$ an exact identity). From the scaling $A(cx)=c^{2}\,A(x)+\tfrac{(cx)^{2}}{2}\log c$ (for $c,x>0$), taking $c=m$ yields

Forming the linear combination with coefficients $+1,-2,+1$ for $k=2,1,0$ respectively,

where the coefficient of $\log m$ is $[(K+2m)^{2}-2(K+m)^{2}+K^{2}]/2=m^{2}\text{.}$ Similarly, $A(2m)-2A(m)=2m^{2}\log(2m)-m^{2}\log m=2m^{2}\log 2+m^{2}\log m\text{.}$ Subtracting and applying Lemma 10 (the closed form of $\varphi$),

By Lemma 13, it suffices to show that the correction term $-\tfrac{1}{12}\log\frac{mK(K+2m)}{2(K+m)^{2}}$ is uniformly $O(\log m)$ over $m\geq 2$ and $K\geq 1\text{.}$

Upper bound. From $(K+m)^{2}-K(K+2m)=m^{2}\geq 0\text{,}$ we have $K(K+2m)\leq(K+m)^{2}\text{,}$ hence

Lower bound. Rewriting the ratio as $\tfrac{m}{2}\bigl(1-m^{2}/(K+m)^{2}\bigr)$ and using $(K+m)^{2}\geq(1+m)^{2}$ for $m\geq 2\text{,}$ $K\geq 1\text{,}$

For $m\geq 2\text{,}$ $m(2m+1)-(m+1)^{2}=m^{2}-m-1\geq 0\text{,}$ so $\frac{mK(K+2m)}{2(K+m)^{2}}\geq\frac{1}{2}\text{.}$

Combining the two bounds, $1/2\leq\frac{mK(K+2m)}{2(K+m)^{2}}\leq m/2\text{,}$ so $\log\frac{mK(K+2m)}{2(K+m)^{2}}\in[-\log 2,\,\log(m/2)]\text{,}$ whose absolute value is at most $\max\{\log 2,\log(m/2)\}\leq\log m$ (for $m\geq 2\text{,}$ both $\log 2\leq\log m$ and $\log(m/2)\leq\log m$). Therefore $\bigl|\tfrac{1}{12}\log\frac{mK(K+2m)}{2(K+m)^{2}}\bigr|\leq\tfrac{1}{12}\log m=O(\log m)\text{,}$ uniformly in $K\text{.}$ The $O(1)$ term in Lemma 13 is also $O(\log m)\text{.}$ ∎

By Lemma 13, $H_{[m]^{2}}(K)-m^{2}\,\varphi=-\tfrac{1}{12}\log\frac{mK(K+2m)}{2(K+m)^{2}}+E\text{,}$ where $|E|\leq C_{1}^{*}$ uniformly over $m,K\geq 1$ for some absolute constant $C_{1}^{*}\geq 0\text{.}$ The proof of Lemma 14 above established $\bigl|\tfrac{1}{12}\log\frac{mK(K+2m)}{2(K+m)^{2}}\bigr|\leq\tfrac{1}{12}\log m$ for $m\geq 2\text{,}$ $K\geq 1\text{.}$ Combining, $|H_{[m]^{2}}(K)-m^{2}\,\varphi|\leq\tfrac{1}{12}\log m+C_{1}^{*}\text{.}$

Bounding $C_{1}^{*}\text{.}$ From the aggregation in Step 2 of the proof of Lemma 13, $E=\zeta^{\prime}(-1)+R\text{,}$ where $|\zeta^{\prime}(-1)|<1/6$ (the standard value is $\zeta^{\prime}(-1)\approx-0.1654$) and $R=\sum_{i=1}^{5}c_{i}\,\mathrm{tail}(z_{i})$ with $z_{i}\in\{K,\,K{+}m,\,K{+}2m,\,m,\,2m\}\text{,}$ $c_{i}=(+1,-2,+1,-1,+2)\text{,}$ and $\sum_{i}|c_{i}|=7\text{.}$ The remainder in (17) is the sum of the tails of the two classical series behind it, Binet’s for $z\log\Gamma(z+1)$ [Olver et al., 2026, §5.11(ii)] and Barnes’s own for the rest [Nemes, 2014, Thm. 1.2]; on the positive real axis each carries the sign of its first omitted term and is smaller in magnitude. Those first omitted terms are $B_{4}/(12z^{2})$ and $B_{4}/(24z^{2})\text{,}$ so

at $z=1$ the remainder is exactly $\tfrac{3}{4}-\tfrac{1}{2}\log(2\pi)-\zeta^{\prime}(-1)=-0.00352\ldots$ Hence $|R|\leq 7\cdot(1/100)=7/100\text{,}$ so $C_{1}^{*}\leq|\zeta^{\prime}(-1)|+|R|<1/6+7/100<1/4\leq 1\text{.}$ Setting $C_{1}:=1$ completes the proof. ∎

Let $F(\alpha):=2\varphi(\alpha)+c/(4\alpha^{2})\text{,}$ so that $\psi(c)=\inf_{\alpha>0}F(\alpha)\text{.}$ Since $F$ is continuous on $(0,\infty)\text{,}$ blows up at $0$ through the penalty term, and diverges at infinity by Lemma 11(f), the infimum is attained on $(0,\infty)\text{.}$

(a). We split into $\alpha\leq 1$ and $\alpha>1\text{.}$

Combining the two cases, $\psi(c)\geq\min(A\,c^{1/3},\,B)\text{.}$

(b).

For $\alpha\in(0,\epsilon_{0}]\text{,}$ AM-GM applied to $(2\log 2-\eta)\alpha+(2\log 2-\eta)\alpha+c/(4\alpha^{2})$ gives

For $\alpha>\epsilon_{0}\text{,}$ $F(\alpha)\geq 2\varphi(\alpha)\geq 2\varphi(\epsilon_{0})>0\text{,}$ a positive constant independent of $c\text{.}$

Since $3(\log 2-\eta/2)^{2/3}c^{1/3}\to 0$ as $c\to 0\text{,}$ there exists $c_{\eta}>0$ such that $3(\log 2-\eta/2)^{2/3}c^{1/3}<2\varphi(\epsilon_{0})$ for $c\leq c_{\eta}\text{,}$ and consequently

Since $\eta>0$ was arbitrary, $\liminf_{c\to 0^{+}}\psi(c)/\bigl(3(\log 2)^{2/3}c^{1/3}\bigr)\geq 1\text{.}$ Combined with the upper bound $\psi(c)\leq 3(\log 2)^{2/3}c^{1/3}\text{,}$ this yields (b).

(c).

Combining the two bounds, $\psi(c)-\log c\in[1-4\log 2,\,5-2\log 2]$ uniformly for $c\geq 1\text{,}$ that is, $\psi(c)=\log c+O(1)\text{.}$ ∎

The proof proceeds in four steps.

Step 1 (Error propagation). By Corollary 15, there exists an absolute constant $\kappa$ (one may take $\kappa:=1/12+1/\log 2<1.53$) such that

(combining the $\tfrac{1}{12}\log m+C_{1}$ form of Corollary 15 with $C_{1}\leq 1\leq(1/\log 2)\log m$ for $m\geq 2$). Hence $|2H_{[m]^{2}}(K)+T/(4K^{2})-(2m^{2}\,\varphi(K/m)+T/(4K^{2}))|\leq 2\kappa\log m$ uniformly in $K\text{.}$ Taking the infimum over $K\text{,}$

where $M_{m}(T):=\inf_{K\in\mathbb{N},\,K\geq 1}\bigl[2m^{2}\,\varphi(K/m)+T/(4K^{2})\bigr]\text{.}$

Step 2 (Continuous relaxation). Define $\tilde{M}_{m}(T):=\inf_{k>0}\bigl[2m^{2}\,\varphi(k/m)+T/(4k^{2})\bigr]\text{.}$ Substituting $\alpha:=k/m\text{,}$

Since $\{K\in\mathbb{N}:K\geq 1\}\subset(0,\infty)\text{,}$

Step 3 (Discretization gap). Let $F(k):=2m^{2}\,\varphi(k/m)+T/(4k^{2})\text{.}$ Since $F$ is continuous on $(0,\infty)\text{,}$ blows up at $0$ through the penalty term, and diverges at infinity by Lemma 11(f), $F$ attains its minimum on $(0,\infty)\text{;}$ let $k_{c}$ denote a minimizer. The first-order condition gives

where the final inequality uses that $\varphi^{\prime}$ is decreasing (Lemma 11(c)) with $\varphi^{\prime}(0)=2\log 2\text{.}$ From (26), $k_{c}\geq(T/(8m\log 2))^{1/3}\text{,}$ so $T/m\to\infty$ implies $k_{c}\to\infty\text{.}$ Choose $T_{0}$ so that $T/m\geq T_{0}$ implies $k_{c}\geq 2$ (one may take $T_{0}:=64\log 2$).

Let $\hat{K}_{c}:=\mathrm{round}(k_{c})\in\mathbb{N}\text{,}$ so $|\hat{K}_{c}-k_{c}|\leq 1/2\text{.}$ From $k_{c}\geq 2\text{,}$ $\hat{K}_{c}\geq k_{c}-1/2\geq 3/2\text{,}$ and as an integer $\hat{K}_{c}\geq 2\text{;}$ moreover, $\hat{K}_{c}\in[k_{c}/2,\,3k_{c}/2]\text{.}$

Step 4 (Combining). From (23), (24), and (27),

Let $c:=T/m^{4}\text{.}$ By Theorem 17, $\Psi_{[m]^{2}}(T)=m^{2}\,\psi(c)+O(m)\text{.}$

By Corollary 15, for all integers $m\geq 2$ and $K\geq 1\text{,}$

By Lemma 11(d), $\varphi(K/m)\leq 2(\log 2)\,K/m\text{,}$ so $2m^{2}\,\varphi(K/m)\leq 4(\log 2)\,mK\text{.}$ Hence, for any integer $K\geq 1\text{,}$

Continuous optimization. The function $G$ is strictly convex on $k>0\text{,}$ with $G^{\prime}(k)=4(\log 2)\,m-T/(2k^{3})\text{.}$ The first-order condition gives the unique minimizer $k_{c}:=\bigl(T/(8(\log 2)\,m)\bigr)^{1/3}\text{.}$ From $T/k_{c}^{3}=8(\log 2)\,m\text{,}$ we have $T/(4k_{c}^{2})=2(\log 2)\,m\,k_{c}\text{,}$ so

where the last equality follows from $m\,k_{c}=m^{2/3}T^{1/3}/(8(\log 2))^{1/3}=m^{2/3}T^{1/3}/(2(\log 2)^{1/3})\text{.}$

Integerization. Set $K_{0}:=\max(1,\,\lceil k_{c}\rceil)\in\mathbb{N}\text{,}$ so $K_{0}\geq 1\text{.}$ We claim $G(K_{0})-G(k_{c})\leq 4(\log 2)\,m\text{.}$

Case 1 ($k_{c}\geq 1$). Here $K_{0}=\lceil k_{c}\rceil$ and $K_{0}-k_{c}\leq 1\text{.}$ The derivative $G^{\prime}$ is strictly increasing on $(k_{c},\infty)$ with values in $(0,4(\log 2)\,m)$ (using $G^{\prime}(k_{c})=0$ and $G^{\prime}(k)\to 4(\log 2)\,m$ as $k\to\infty$). By the mean value theorem, there exists $\xi\in(k_{c},K_{0})$ with $G(K_{0})-G(k_{c})=G^{\prime}(\xi)(K_{0}-k_{c})\leq 4(\log 2)\,m\text{.}$

Case 2 ($k_{c}<1$). Here $K_{0}=1$ and $1-k_{c}<1\text{.}$ Since $G$ is convex and $G^{\prime}$ on $(k_{c},1]\subset(k_{c},\infty)$ takes values in $(0,G^{\prime}(1)]$ with $G^{\prime}(1)=4(\log 2)\,m-T/2\text{,}$ and since $k_{c}<1$ is equivalent to $T<8(\log 2)\,m\text{,}$ one has $G^{\prime}(1)\geq 0$ and $G^{\prime}(1)\leq 4(\log 2)\,m\text{.}$ The mean value theorem gives $G(1)-G(k_{c})\leq G^{\prime}(1)(1-k_{c})<4(\log 2)\,m\text{.}$

Combining the two cases, for all $T>0\text{,}$

Low-order term absorption. From $T\geq m\text{,}$ $m\leq m^{2/3}\,T^{1/3}\text{;}$ combined with $m\geq 16\text{,}$ $m^{2/3}\,T^{1/3}\geq m\geq 16\text{.}$ Hence $4(\log 2)\,m\leq 4(\log 2)\,m^{2/3}\,T^{1/3}\text{;}$ using $\log m\leq m\text{,}$ $\tfrac{1}{6}\log m\leq\tfrac{1}{6}\,m^{2/3}\,T^{1/3}\text{;}$ using $C_{1}\geq 0$ and $m^{2/3}\,T^{1/3}\geq 16\text{,}$ $2C_{1}\leq(C_{1}/8)\,m^{2/3}\,T^{1/3}\text{.}$ Combining,

Numerically, $3\,(\log 2)^{2/3}+4(\log 2)+1/6\approx 5.30\text{;}$ combined with $C_{1}\leq 1$ (so $C_{1}/8\leq 1/8$), $\Psi_{[m]^{2}}(T)\leq 5.43\,m^{2/3}\,T^{1/3}\leq 6\,m^{2/3}\,T^{1/3}\text{,}$ which is (31). ∎

Set $K^{*}:=\lceil\sqrt{T}/(2m)\rceil\in\mathbb{N}\text{.}$ From $T\geq m^{4}\text{,}$ $\sqrt{T}/(2m)\geq m/2\text{,}$ so $K^{*}\geq\lceil m/2\rceil\geq m/2\text{;}$ in particular, $K^{*}/m\geq 1/2\text{,}$ and the hypothesis of Lemma 11(e) is satisfied.

Entropy term. By Corollary 15 and Lemma 11(e),

From $K^{*}\leq\sqrt{T}/(2m)+1\text{,}$

From $T\geq m^{4}\text{,}$ $\sqrt{T}\geq m^{2}\text{,}$ so $2m/\sqrt{T}\leq 2/m\text{;}$ combined with $m\geq 16\text{,}$ $2/m\leq 1/8\text{,}$ so $\log(1+2m/\sqrt{T})\leq\log(9/8)<1/8\text{.}$ Substituting,

Penalty term. $K^{*}\geq\sqrt{T}/(2m)$ implies $(K^{*})^{2}\geq T/(4m^{2})\text{,}$ so

Combining. Setting $K=K^{*}$ in the definition of $\Psi\text{,}$ $\Psi_{[m]^{2}}(T)\leq 2H_{[m]^{2}}(K^{*})+T/(4(K^{*})^{2})\text{.}$ Combining the entropy estimates,

and adding the penalty term $T/(4(K^{*})^{2})\leq m^{2}\text{,}$ we collect the $m^{2}$ coefficients ($-2\log 2+1/4+4+1=21/4-2\log 2$) to obtain

Low-order term absorption. $\tfrac{21}{4}-2\log 2\approx 3.864\text{.}$ For $m\geq 16\text{,}$ $\log m\leq m\leq m^{2}/16\text{,}$ so $\tfrac{1}{6}\log m\leq m^{2}/96\text{;}$ from $m^{2}\geq 256$ and $C_{1}\geq 0\text{,}$ $2C_{1}\leq(C_{1}/128)\,m^{2}\text{.}$ Hence

With $C_{1}\leq 1\text{,}$ $3.864+1/96+1/128<3.89<6\text{,}$ giving (34). ∎

The argument partitions the parameter range into four intervals A, B, C, D, each yielding an independent constant $c_{A},c_{B},c_{C},c_{D}\text{;}$ the final constant is $c:=\min\{c_{A},c_{B},c_{C},c_{D}\}\text{.}$

Interval A ($T\leq 15m$). Take $K=1\in[1,\lfloor m/8\rfloor]$ (the bound $\lfloor m/8\rfloor\geq 2$ follows from $m\geq 16$). Then

If $T\leq m\text{,}$ then $L_{1}\geq T\geq\min\{T,\Psi_{[m]^{2}}(T)\}\text{,}$ giving $c_{A}^{(1)}=1\text{.}$ If $m<T\leq 15m\text{,}$ then $L_{1}\geq m\geq T/15\geq\min\{T,\Psi_{[m]^{2}}(T)\}/15\text{,}$ giving $c_{A}^{(2)}=1/15\text{.}$ Combining, $c_{A}:=1/15\text{.}$

Interval B ($15m<T\leq m^{4}/512$). Let $k_{\mathrm{bal}}:=(T/m)^{1/3}$ be the continuous balance point of $\min\{mk,T/k^{2}\}\text{;}$ at this point, $m\,k_{\mathrm{bal}}=T/k_{\mathrm{bal}}^{2}=m^{2/3}\,T^{1/3}\text{.}$ From $T>15m\text{,}$ $k_{\mathrm{bal}}>15^{1/3}>2\text{.}$ From $T\leq m^{4}/512\text{,}$ $k_{\mathrm{bal}}\leq(m^{3}/512)^{1/3}=m/8\text{.}$

Set $K_{0}:=\lfloor k_{\mathrm{bal}}\rfloor\in\mathbb{N}\text{.}$ Since $k_{\mathrm{bal}}>2\text{,}$ $K_{0}\geq k_{\mathrm{bal}}/2$ (using $\lfloor x\rfloor\geq x/2$ for $x\geq 2$); thus $K_{0}\leq\lfloor m/8\rfloor\text{,}$ so $K_{0}$ is admissible. We have

Therefore $L_{1}\geq\min(mK_{0},\,T/K_{0}^{2})\geq m^{2/3}\,T^{1/3}/2\text{.}$ On the other hand, by Lemma 20, $\Psi_{[m]^{2}}(T)\leq 6\,m^{2/3}\,T^{1/3}\text{,}$ so $\min\{T,\Psi_{[m]^{2}}(T)\}\leq\Psi_{[m]^{2}}(T)\leq 6\,m^{2/3}\,T^{1/3}\leq 12\,L_{1}\text{.}$ Combining, $c_{B}:=1/12\text{.}$

Interval C ($m^{4}/512<T\leq C_{0}^{2}\,m^{4}$). Take $K=\lfloor m/8\rfloor\text{.}$ From $m\geq 16\text{,}$ $\lfloor m/8\rfloor\geq m/8-1\geq m/16$ (the second inequality is equivalent to $m\geq 16$). Hence

From $T>m^{4}/512\text{,}$ $64\,T/m^{2}>64\,m^{2}/512=m^{2}/8>m^{2}/16\text{,}$ so $L_{1}\geq m^{2}/16\text{.}$

The upper bound on $\Psi$ is obtained by combining two sub-intervals:

• •

  For $T\leq m^{4}\text{,}$ Lemma 20 gives $\Psi_{[m]^{2}}(T)\leq 6\,m^{2/3}\,T^{1/3}\leq 6\,m^{2/3}\cdot m^{4/3}=6\,m^{2}\text{.}$

• •

  For $m^{4}<T\leq C_{0}^{2}\,m^{4}\text{,}$ Lemma 21 gives $\Psi_{[m]^{2}}(T)\leq m^{2}\log(T/m^{4})+6\,m^{2}\leq m^{2}\cdot 2\log C_{0}+6\,m^{2}=(2\log C_{0}+6)\,m^{2}\text{.}$

Let $B^{*}:=2\log C_{0}+6\text{.}$ With $C_{0}=2160\text{,}$ the bound $\log 2160<7.679$ (numerically verified) gives $B^{*}<21.358\text{.}$ Since $B^{*}>6\text{,}$ the two sub-intervals unify to $\Psi_{[m]^{2}}(T)\leq B^{*}\,m^{2}\leq 22\,m^{2}\text{.}$

Combining, $L_{1}\geq m^{2}/16\geq\Psi_{[m]^{2}}(T)/(16\,B^{*})\text{.}$ Since $16\,B^{*}<16\cdot 21.358=341.728<342\text{,}$ $1/(16\,B^{*})>1/342\text{;}$ setting $c_{C}:=1/342$ gives $L_{1}\geq c_{C}\cdot\Psi_{[m]^{2}}(T)\geq c_{C}\cdot\min\{T,\Psi_{[m]^{2}}(T)\}\text{.}$

Interval D ($T>C_{0}^{2}\,m^{4}$). From $T>C_{0}^{2}\,m^{4}\text{,}$ $T/(C_{0}\,m^{4})>C_{0}\geq 1\text{,}$ so

Since $T>C_{0}^{2}\,m^{4}\text{,}$ $\log(T/m^{4})>2\log C_{0}\text{,}$ so $\log C_{0}<\log(T/m^{4})/2\text{.}$ Hence

On the other hand, Lemma 21 gives $\Psi_{[m]^{2}}(T)\leq m^{2}\log(T/m^{4})+6\,m^{2}\text{.}$ Since $\log(T/m^{4})>2\log C_{0}\approx 15.36>15\text{,}$ $6\,m^{2}<(6/15)\,m^{2}\log(T/m^{4})=(2/5)\,m^{2}\log(T/m^{4})\text{,}$ so $\Psi_{[m]^{2}}(T)<(7/5)\,m^{2}\log(T/m^{4})\text{.}$

Combining, $L_{2}/\Psi_{[m]^{2}}(T)>(1/2)/(7/5)=5/14>1/3\text{.}$ Since $\min\{T,\Psi_{[m]^{2}}(T)\}\leq\Psi_{[m]^{2}}(T)\text{,}$ this gives $L_{2}>\min\{T,\Psi_{[m]^{2}}(T)\}/3\text{,}$ and we set $c_{D}:=1/3\text{.}$

Combining intervals. $c:=\min\{c_{A},c_{B},c_{C},c_{D}\}=\min\{1/15,\,1/12,\,1/342,\,1/3\}=1/342\text{.}$ Intervals A, B, and C give $L_{1}\geq c\cdot\min\{T,\Psi_{[m]^{2}}(T)\}$ for all $T\leq C_{0}^{2}\,m^{4}\text{;}$ Interval D gives $L_{2}\geq c\cdot\min\{T,\Psi_{[m]^{2}}(T)\}$ for $T>C_{0}^{2}\,m^{4}\text{.}$ In either range, $\max\{L_{1},L_{2}\}$ inherits the corresponding bound, so

for all integers $m\geq 16$ and $T\geq 1\text{.}$ ∎

Three exhaustive cases cover the parameter range: (a) $m\geq 16\text{;}$ (b) $2\leq m\leq 15$ with $T\leq C_{0}^{2}\,m^{4}\text{;}$ (c) $2\leq m\leq 15$ with $T>C_{0}^{2}\,m^{4}\text{.}$ Throughout, $c_{1}:=1/1088$ is the LB-I constant (Lemma 26, valid for all $T\geq 1$), $c_{2}:=3/16$ is the LB-II constant (Lemma 31, valid for $T\geq m^{2}$), and $c_{BL}:=1/342$ is the constant from Lemma 19.

Case (a). The separated form of Lemma 19 combined with LB-I and LB-II gives:

• •

  For $T\leq C_{0}^{2}\,m^{4}\text{,}$ $L_{1}\geq c_{BL}\,\min\{T,\Psi_{[m]^{2}}(T)\}\text{,}$ and LB-I applies, yielding $R_{T}^{*}\geq c_{1}\,c_{BL}\,\min\{T,\Psi_{[m]^{2}}(T)\}\text{.}$

• •

  For $T>C_{0}^{2}\,m^{4}\text{,}$ $L_{2}\geq c_{BL}\,\min\{T,\Psi_{[m]^{2}}(T)\}\text{.}$ Since $T>C_{0}^{2}\,m^{4}\geq m^{2}\text{,}$ LB-II applies, yielding $R_{T}^{*}\geq c_{2}\,c_{BL}\,\min\{T,\Psi_{[m]^{2}}(T)\}\text{.}$

Since $c_{1}<c_{2}$ ($1/1088<3/16$), set $c^{(a)}:=c_{BL}\,c_{1}=(1/342)(1/1088)=1/372096\text{.}$

Case (b). Trivial-adversary lower bound. Fix a grid point $x_{0}\in[m]^{2}$ and a constant label $b\in\{0,1\}\text{.}$ Any randomized learner’s first-round prediction $\hat{y}_{1}$ is a $[0,1]$-valued random variable. Since $\hat{y}_{1}^{2}+(1{-}\hat{y}_{1})^{2}\geq 1/2$ pointwise, linearity of expectation gives $\mathbb{E}[\hat{y}_{1}^{2}]+\mathbb{E}[(1{-}\hat{y}_{1})^{2}]\geq 1/2\text{,}$ so $\max_{b\in\{0,1\}}\mathbb{E}[(\hat{y}_{1}-b)^{2}]\geq 1/4\text{.}$ Letting $b^{*}$ achieve this maximum, the comparator $f\equiv b^{*}\in\mathcal{F}_{[m]^{2}}^{\uparrow}$ has zero loss; taking the Yao expectation over the adversary’s prior $\mathrm{Unif}\{0,1\}$ yields $R_{T}^{*}\geq 1/4\text{.}$

$\Psi$ upper bounds for $m\geq 2\text{.}$ The proofs of Lemmas 20 and 21 are independent of $m\geq 16$ except for the low-order term absorption step. Redoing that step for $m\geq 2\text{:}$

• •

  (Lemma 20 for $m\geq 2\text{,}$ $T\geq m\text{.}$) From $m^{2/3}\,T^{1/3}\geq m\geq 2\text{,}$ $2C_{1}\leq m^{2/3}\,T^{1/3}$ (using $C_{1}\leq 1$); the other terms are unchanged. Combining,

  $$\Psi_{[m]^{2}}(T)\;\leq\;\bigl[3\,(\log 2)^{2/3}+4\log 2+\tfrac{1}{6}+1\bigr]\,m^{2/3}\,T^{1/3}\;<\;7\,m^{2/3}\,T^{1/3}.$$

  (35)

• •

  (Lemma 21 for $m\geq 2\text{,}$ $T\geq m^{4}\text{.}$) From $2m/\sqrt{T}\leq 2/m\leq 1\text{,}$ so $\log(1+2m/\sqrt{T})\leq\log 2$ and the $m^{2}$ coefficient before absorption is $5$ in place of $\tfrac{21}{4}-2\log 2\text{;}$ and from $\log m\leq m\leq m^{2}/2$ and $m^{2}\geq 4\text{,}$ $\tfrac{1}{6}\log m\leq m^{2}/12$ and $2C_{1}\leq m^{2}/2\text{.}$ Combining,

  $$\Psi_{[m]^{2}}(T)\;\leq\;m^{2}\log(T/m^{4})+\bigl[5+\tfrac{1}{12}+\tfrac{1}{2}\bigr]\,m^{2}\;<\;m^{2}\log(T/m^{4})+6\,m^{2}.$$

  (36)

Let $B^{\prime}:=2\log C_{0}+6\approx 21.36\text{.}$ The bound $\min\{T,\Psi_{[m]^{2}}(T)\}\leq B^{\prime}\,m^{2}$ holds for all $2\leq m\leq 15$ and $T\leq C_{0}^{2}\,m^{4}\text{,}$ from a three-way sub-interval split:

• •

  For $T<m\text{,}$ $\min\{T,\Psi_{[m]^{2}}(T)\}\leq T<m\leq m^{2}<B^{\prime}\,m^{2}\text{.}$

• •

  For $m\leq T\leq m^{4}\text{,}$ by (35), $\Psi_{[m]^{2}}(T)\leq 7\,m^{2/3}\,T^{1/3}\leq 7\,m^{2}<B^{\prime}\,m^{2}\text{.}$

• •

  For $m^{4}<T\leq C_{0}^{2}\,m^{4}\text{,}$ by (36), $\Psi_{[m]^{2}}(T)\leq m^{2}\cdot 2\log C_{0}+6\,m^{2}=B^{\prime}\,m^{2}\text{.}$

Combined with $m\leq 15\text{,}$ $\min\{T,\Psi_{[m]^{2}}(T)\}\leq 225\,B^{\prime}\text{.}$ Hence $R_{T}^{*}\geq 1/4\geq\min\{T,\Psi_{[m]^{2}}(T)\}/(900\,B^{\prime})\text{,}$ giving $c^{(b)}:=1/(900\,B^{\prime})\approx 1/19221\text{.}$

Case (c). The argument paralleling Interval D of the proof of Lemma 19, based on the $m\geq 2$ Phase 2 upper bound (36) and the definition of $L_{2}\text{,}$ proceeds as follows. The first step $L_{2}\geq m^{2}\log(T/m^{4})/2$ is independent of the size of $m$ (as in Interval D). The second step uses (36): $\Psi_{[m]^{2}}(T)\leq m^{2}\log(T/m^{4})+6\,m^{2}\text{.}$ Since $\log(T/m^{4})>2\log C_{0}>15\text{,}$ $6\,m^{2}<(2/5)\,m^{2}\log(T/m^{4})\text{,}$ so $\Psi_{[m]^{2}}(T)<(7/5)\,m^{2}\log(T/m^{4})$ and $L_{2}/\Psi_{[m]^{2}}(T)>(1/2)/(7/5)=5/14\text{,}$ i.e., $L_{2}\geq\Psi_{[m]^{2}}(T)/2.8\text{.}$

Since $T>C_{0}^{2}\,m^{4}\geq m^{2}\text{,}$ LB-II applies:

giving $c^{(c)}:=15/224\approx 1/14.9\text{.}$

Combining the three cases. $c:=\min\{c^{(a)},c^{(b)},c^{(c)}\}=\min\{1/372096,\,1/(900\,B^{\prime}),\,15/224\}=1/372096\text{,}$ with Case (a) being binding. ∎

The proof perturbs the complete level set. Fix a value $c$ attained by $f^{*}$ and let $C_{c}:=\{u\in\mathcal{P}:f^{*}(u)=c\}\text{,}$ so that $B_{c}=\{u\in C_{c}:w_{u}>0\}\text{,}$ and perturb the whole of it uniformly:

If $u\in C_{c}\text{,}$ $v\notin C_{c}\text{,}$ and $u\prec v\text{,}$ then $f^{*}(v)\geq c$ and $f^{*}(v)\neq c\text{,}$ so $f^{*}(v)>c\text{;}$ symmetrically, $f^{*}(u)<c$ whenever $u\notin C_{c}\text{,}$ $v\in C_{c}\text{,}$ $u\prec v\text{.}$ Since $\mathcal{P}$ is finite, there is $\epsilon_{0}>0$ smaller than all these gaps, and smaller than $\min\{c,1-c\}$ when $c\in(0,1)\text{.}$ For $|\epsilon|\leq\epsilon_{0}$ the function $f_{\epsilon}$ is then order-preserving: pairs inside or outside $C_{c}$ keep their differences, and pairs across the boundary retain a positive gap. Its values lie in $[0,1]$ for $|\epsilon|\leq\epsilon_{0}$ when $c\in(0,1)\text{,}$ for $\epsilon\in[0,\epsilon_{0}]$ when $c=0\text{,}$ and for $\epsilon\in[-\epsilon_{0},0]$ when $c=1\text{;}$ at $c=0$ no element of $\mathcal{P}$ lies below $C_{c}$ with a smaller value, so only the upward comparisons matter, and symmetrically at $c=1\text{.}$

Only the rounds with $x_{t}\in B_{c}$ see the perturbation, so

is minimized at $\epsilon=0$ over the admissible range, and $F(0)\leq L_{T}(f^{*})<\infty\text{.}$ For $c\in(0,1)\text{,}$ each summand is finite and differentiable on a two-sided neighborhood of $c\text{,}$ since a convex function is finite where it is differentiable; an interior minimum of the differentiable $F$ gives

For $c=0\text{,}$ convexity gives each summand a right derivative in $[-\infty,\infty)$ at $0\text{,}$ and the right derivative of the finite sum is the sum of right derivatives; if that sum were negative, $F$ would take values below $F(0)$ arbitrarily close to $0\text{,}$ contradicting minimality. The case $c=1$ is symmetric. ∎

Let $\mathcal{F}_{K}$ be the isotonic $G_{K}$-valued functions, $\log|\mathcal{F}_{K}|=H_{\mathcal{P}}(K)\text{.}$ The learner, knowing $T\text{,}$ fixes $K$ at the minimizer of the stated bound, runs exponential weights over $\mathcal{F}_{K}$ at rate $\eta\text{,}$ and predicts the weighted mean; it is deterministic, and the bound follows from the aggregation and rounding estimates below.

Aggregation. Let $w_{t}(f):=\exp(-\eta\sum_{s<t}\ell(f(x_{s}),y_{s}))\text{,}$ $W_{t}:=\sum_{f\in\mathcal{F}_{K}}w_{t}(f)\text{,}$ $q_{t}(f):=w_{t}(f)/W_{t}\text{,}$ and $\hat{y}_{t}:=\mathbb{E}_{f\sim q_{t}}[f(x_{t})]\text{.}$ Concavity of $p\mapsto e^{-\eta\ell(p,y_{t})}$ and Jensen’s inequality give

so summing $\ell(\hat{y}_{t},y_{t})\leq-\tfrac{1}{\eta}\log(W_{t+1}/W_{t})$ over $t$ and using $W_{T+1}\geq w_{T+1}(\hat{f})=e^{-\eta L_{T}(\hat{f})}$ for any $\hat{f}\in\mathcal{F}_{K}\text{,}$

Rounding. Smoothness makes $\ell(\cdot,y)$ finite and continuous on $[0,1]\text{,}$ so a minimizer $f^{*}$ of $L_{T}$ over the compact $\mathcal{F}_{\mathcal{P}}^{\uparrow}$ exists and Lemma 50 applies. Let $q$ be nearest-grid rounding onto $G_{K}$ and $\hat{f}:=q\circ f^{*}\in\mathcal{F}_{K}\text{;}$ each offset $\delta_{c}:=q(c)-c$ obeys $|\delta_{c}|\leq\tfrac{1}{2K}\text{,}$ with $\delta_{0}=\delta_{1}=0$ since $0,1\in G_{K}\text{.}$ By the Taylor bound for a loss with $\beta$-Lipschitz derivative, for every $t$ with $x_{t}\in B_{c}\text{,}$

Summing over $\{t:x_{t}\in B_{c}\}\text{,}$ the first-order term vanishes: at interior levels by Lemma 50, and at $c\in\{0,1\}$ because $\delta_{c}=0\text{.}$ Summing over the levels and using $\sum_{c}w_{B_{c}}=T\text{,}$

Combining the two estimates gives $R_{T}\leq\tfrac{1}{\eta}H_{\mathcal{P}}(K)+\tfrac{\beta T}{8K^{2}}$ at the chosen $K\text{,}$ hence at the infimum; the squared loss has $(\eta,\beta)=(\tfrac{1}{2},2)\text{,}$ giving (2), and a bound achieved by a deterministic learner on every sequence bounds the minimax regret. ∎

(a) and (b). In each of the two proofs, the loss enters at exactly one step, the reduction of regret to estimation error, and every later step concerns the Bernoulli observation law alone. In the proof of Lemma 59, the adversary plays $f_{\theta}\in\mathcal{F}_{\mathcal{P}}^{\uparrow}$ with values in $[\tfrac{1}{4},\tfrac{3}{4}]$ and Bernoulli labels; for any loss, $R_{T}\geq\sum_{t}[\ell(\hat{y}_{t},Y_{t})-\ell(f_{\theta}(x_{t}),Y_{t})]\text{,}$ and conditionally on $\theta$ and the past, $Y_{t}\sim\mathrm{Ber}(f_{\theta}(x_{t}))$ with $\hat{y}_{t}$ measurable, so (1) with $p=f_{\theta}(x_{t})\in[\tfrac{1}{4},\tfrac{3}{4}]$ gives

The right-hand sum is the quantity the remainder of that proof bounds from below, so the conclusion holds with the extra factor $\alpha\text{.}$ The same substitution applies in the proof of Lemma 60, whose adversary plays $P\in\mathcal{F}_{\mathcal{P}}^{\uparrow}$ with values in $[\tfrac{1}{4},\tfrac{3}{4}]\text{:}$ the regret-to-estimation step, Step A of Section E.2, is replaced by the display above, and the remaining steps bound the estimation sum alone.

(c). Assume $W\neq\varnothing\text{,}$ the claim being trivial otherwise. Sample $\sigma_{a}\in\{\tfrac{1}{4},\tfrac{3}{4}\}$ uniformly and independently for $a\in W\text{,}$ and let $f_{\sigma}\in\mathcal{F}_{\mathcal{P}}^{\uparrow}$ extend $\sigma\text{.}$ The adversary queries $s:=\min\{T,|W|\}$ distinct points $a_{1},\ldots,a_{s}$ of $W$ once each, then queries $a_{1}$ for the remaining rounds; all labels are $Y_{t}\sim\mathrm{Ber}(f_{\sigma}(x_{t}))\text{,}$ drawn independently, and every queried value is $\sigma_{a_{t}}\in\{\tfrac{1}{4},\tfrac{3}{4}\}\text{.}$ Since $f_{\sigma}\in\mathcal{F}_{\mathcal{P}}^{\uparrow}\text{,}$ the display above applies and the terms with $t>s$ are nonnegative, so

At round $t\leq s$ the point $a_{t}$ has not been queried before, and the earlier labels are generated from the values of $\sigma$ at other points, so $\hat{y}_{t}$ is independent of $\sigma_{a_{t}}\text{;}$ hence $\mathbb{E}[(\hat{y}_{t}-\sigma_{a_{t}})^{2}]\geq\mathrm{Var}(\sigma_{a_{t}})=\tfrac{1}{16}\text{.}$ Summing and applying Yao’s principle gives the claim.

(d). The upper bound is Theorem 1 or Theorem 55 with $R_{T}\leq\Lambda T\text{,}$ respectively $R_{T}\leq T\log 2\text{,}$ and the homogeneity comparison of Section 2.3. For the lower bound, the noisy-bisection adversary of Appendix I plays a comparator with values in $(\tfrac{1}{4},\tfrac{3}{4})$ and Bernoulli labels, and the loss enters its analysis only through the reduction of regret to the estimation sums of the stagewise Bayes bounds; the display of (a) performs that reduction for any loss satisfying (1), at the cost of the factor $\alpha\text{,}$ and every later step of that appendix concerns the observation law alone. Its deep-horizon branch specializes the interior-cube construction to one dimension and is the case (b), and its constant-size range follows from (c) with a single-point antichain. The synthesis of Appendix I, which assembles the stagewise bounds into $\min\{T,\Psi_{[n]}(T)\}\text{,}$ is a computation about $\Psi_{[n]}$ and is untouched.

Entropic loss. For $p,q\in(0,1)\text{,}$ expanding both expectations gives

and Pinsker’s inequality in its binary form [Tsybakov, 2009] gives $\mathrm{kl}(p\,\|\,q)\geq 2(p-q)^{2}\text{;}$ the case $q\in\{0,1\}$ has infinite left side. So (1) holds with $\alpha=2\text{.}$ ∎

On $(0,1)\text{,}$ $\partial_{1}\ell_{\phi}(p,y)=-\phi^{\prime\prime}(p)(y-p)\text{.}$ For $c\in(0,1)\text{,}$ the interior identity of Lemma 50, which requires only differentiability on $(0,1)$ by the remark following its proof, gives $\phi^{\prime\prime}(c)\sum_{t:x_{t}\in B_{c}}(y_{t}-c)=0\text{,}$ and $\phi^{\prime\prime}(c)>0$ yields (111).

Let now $c=0$ and $F(\epsilon):=\sum_{t:x_{t}\in B_{0}}\ell_{\phi}(\epsilon,y_{t})\text{,}$ which the perturbation in the proof of Lemma 50 shows is minimized over $[0,\epsilon_{0}]$ at $\epsilon=0\text{;}$ moreover $F(0)\leq L_{T}(f^{*})<\infty\text{,}$ and $F$ is right-continuous at $0\text{,}$ its finitely many summands being defined as limits. On $(0,\epsilon_{0})\text{,}$ $F^{\prime}(\epsilon)=-\phi^{\prime\prime}(\epsilon)\sum_{t}(y_{t}-\epsilon)\text{.}$ If $\sum_{t}y_{t}>0\text{,}$ then $F^{\prime}<0$ on a right neighborhood of $0\text{,}$ so $F$ is strictly decreasing there, and right-continuity places values of $F$ strictly below $F(0)\text{,}$ contradicting minimality. Hence $\sum_{t}y_{t}\leq 0\text{,}$ and $y_{t}\geq 0$ forces every label on $B_{0}$ to vanish, so (111) holds at $c=0$ with both sides zero; the case $c=1$ is symmetric.

For (112) with $c\in(0,1)\text{,}$ expanding the four defining terms verifies

and summing over $\{t:x_{t}\in B_{c}\}$ kills the second term by (111). At $c\in\{0,1\}$ every label on $B_{c}$ equals $c\text{,}$ so each summand is $\ell_{\phi}(z,c)-\ell_{\phi}(c,c)=D_{\phi}(c\,\|\,z)\text{,}$ using $\ell_{\phi}(c,c)=0\text{:}$ for $c=0\text{,}$ say, $\ell_{\phi}(0,0)=\lim_{p\downarrow 0}[\phi(0)-\phi(p)+p\,\phi^{\prime}(p)]=0\text{,}$ since continuity handles the first two terms and convexity traps $p\phi^{\prime}(p)$ between $2[\phi(p)-\phi(p/2)]$ and $\phi(2p)-\phi(p)\text{,}$ both of which vanish. ∎

The $K+1$ cells of length $2h$ partition $[0,\pi/2]\text{,}$ and $\bar{\theta}:=(2k(\theta)+1)h$ is the midpoint of the cell of $\theta\text{,}$ so $|\theta-\bar{\theta}|\leq h\text{;}$ the cell index is nondecreasing in $\theta$ and $\sin^{2}$ increases on $[0,\pi/2]\text{,}$ so $q_{K}$ is nondecreasing.

Suppose first $\theta\leq\pi/4\text{.}$ Since $\pi/4=(K{+}1)h\text{,}$ the index satisfies $2k(\theta)+1\leq K+1\text{,}$ so $h\leq\bar{\theta}\leq\pi/4$ and $\theta\leq\bar{\theta}+h\leq 2\bar{\theta}\text{.}$ Write $z:=\sin^{2}\bar{\theta}\text{.}$ Using $c-z=\sin(\theta+\bar{\theta})\sin(\theta-\bar{\theta})$ and $z(1-z)=\tfrac{1}{4}\sin^{2}(2\bar{\theta})\text{,}$

the first inequality being standard [Tsybakov, 2009]. Bounding $\sin(\theta+\bar{\theta})\leq\theta+\bar{\theta}\leq 3\bar{\theta}\text{,}$ $|\sin(\theta-\bar{\theta})|\leq h\text{,}$ and $\sin(2\bar{\theta})\geq\tfrac{2}{\pi}\,(2\bar{\theta})\text{,}$ the last valid because $2\bar{\theta}\leq\pi/2\text{,}$ gives $\mathrm{kl}(c\,\|\,z)\leq\tfrac{9}{4}\pi^{2}h^{2}=9\pi^{4}/(64(K{+}1)^{2})\text{.}$

If instead $\theta>\pi/4\text{,}$ then $2k(\theta)+1\geq K+1\text{,}$ so $\pi/4\leq\bar{\theta}\leq\pi/2-h\text{.}$ Setting $\theta^{\prime}:=\pi/2-\theta$ and $\bar{\theta}^{\prime}:=\pi/2-\bar{\theta}\text{,}$ the pair $(\theta^{\prime},\bar{\theta}^{\prime})$ satisfies $|\theta^{\prime}-\bar{\theta}^{\prime}|\leq h$ and $h\leq\bar{\theta}^{\prime}\leq\pi/4\text{,}$ hence $\theta^{\prime}\leq 2\bar{\theta}^{\prime}\text{,}$ and $\mathrm{kl}(c\,\|\,z)=\mathrm{kl}(1-c\,\|\,1-z)$ with $1-c=\sin^{2}\theta^{\prime}\text{,}$ $1-z=\sin^{2}\bar{\theta}^{\prime}\text{,}$ so the same computation applies. Finally $9\pi^{4}/64<14$ and $(K+1)^{2}>K^{2}\text{.}$ ∎

Fix $K\text{.}$ The learner runs exponential weights at rate $1$ over the isotonic maps into $Z_{K}\text{,}$ of which there are $\Omega(\mathcal{P},K{+}1)\text{,}$ and predicts the weighted mean, which lies in $[\min Z_{K},\max Z_{K}]\subset(0,1)\text{,}$ so its losses are finite.

Aggregation. The entropic loss is $1$-exp-concave: for $y\in\{0,1\}$ the map $g(p):=e^{-\ell_{\log}(p,y)}=p^{y}(1-p)^{1-y}$ is affine, and for $y\in(0,1)\text{,}$ writing $A:=y/p$ and $B:=(1-y)/(1-p)\text{,}$ one has $(\log g)^{\prime}=A-B$ and $(\log g)^{\prime\prime}=-A^{2}/y-B^{2}/(1-y)\text{,}$ so

by the Cauchy–Schwarz inequality $(A-B)^{2}\leq(y+(1-y))(A^{2}/y+B^{2}/(1-y))\text{.}$ The aggregation estimate in the proof of Theorem 1 therefore applies at rate $\eta=1$ and costs $H_{\mathcal{P}}(K)$ against the best isotonic $Z_{K}$-valued map.

Rounding. With the endpoint values supplied by limits, $\ell_{\log}(\cdot,y)$ is continuous as a $[0,\infty]$-valued function of the prediction, so $L_{T}$ attains its minimum on the compact $\mathcal{F}_{\mathcal{P}}^{\uparrow}\text{;}$ and the constant function $\tfrac{1}{2}\text{,}$ isotonic with $\ell_{\log}(\tfrac{1}{2},y)=\log 2$ for every $y\text{,}$ shows the minimum is at most $T\log 2\text{,}$ so a minimizer $f^{*}$ with finite loss exists. With $\phi(u):=u\log u+(1-u)\log(1-u)\text{,}$ the negative binary entropy, one has $D_{\phi}(y\,\|\,p)=\mathrm{kl}(y\,\|\,p)=\ell_{\log}(p,y)+\phi(y)\text{,}$ and $\phi(y)$ does not depend on the prediction, so $\ell_{\log}$ and $\ell_{\phi}$ have identical regret and identical minimizers. Set $\hat{f}:=q_{K}\circ f^{*}\text{,}$ isotonic and $Z_{K}$-valued by Lemma 54. Applying Lemma 53 blockwise with $z=q_{K}(c)$ and then Lemma 54,

Combining the two estimates and taking the infimum over $K$ gives the theorem. ∎

We establish two bounds on an arbitrary finite poset $\mathcal{P}\text{:}$ a deterministic learner achieves, on every sequence,

and, whenever $\mathcal{P}$ contains an antichain of size $N_{0}\text{,}$

Upper bound. Two strategies realize the two entries of (113); comparing $\rho_{\tau}T$ with $8H_{\mathcal{P}}(1)$ selects the smaller, since $2\sqrt{2\rho_{\tau}TH_{\mathcal{P}}(1)}\leq\rho_{\tau}T$ exactly when $8H_{\mathcal{P}}(1)\leq\rho_{\tau}T\text{.}$ The constant strategy predicts $\hat{y}_{t}\equiv\tau\text{:}$ its per-round loss satisfies $\ell_{\tau}(\tau,y)\leq\rho_{\tau}$ for every $y\in[0,1]\text{,}$ the two branches of the loss contributing at most $\tau(1-\tau)$ and $(1-\tau)\tau\text{,}$ and the comparator loss is nonnegative, so $R_{T}\leq\rho_{\tau}T\text{.}$

For the aggregation strategy, suppose $\rho_{\tau}T\geq 8H_{\mathcal{P}}(1)$ and recall that the $G_{1}$-valued isotonic functions are exactly the indicators of upsets, so their number is $e^{H_{\mathcal{P}}(1)}\text{.}$ The learner runs exponential weights over the experts $\{\mathbf{1}\!\left[\cdot\in U\right]:U\in\mathcal{U}(\mathcal{P})\}$ at rate $\eta:=\sqrt{2H_{\mathcal{P}}(1)/(\rho_{\tau}T)}\leq\tfrac{1}{2}$ and predicts the marginal $p_{t}:=\Pr_{U\sim q_{t}}[x_{t}\in U]$ under the current weight distribution $q_{t}\text{;}$ the losses driving the weights are specified below. For any subgradient $g_{t}\in\partial_{1}\ell_{\tau}(p_{t},y_{t})\subseteq[-\tau,1-\tau]\text{,}$ convexity gives, for every $f\in\mathcal{F}_{\mathcal{P}}^{\uparrow}\text{,}$

and the layer-cake identity $f(x)=\int_{0}^{1}\mathbf{1}\!\left[x\in\{f\geq s\}\right]\,ds\text{,}$ whose level sets $\{f\geq s\}$ are upsets, expresses the right side as an average over $s$ of linearized regrets against single upsets:

Shift the linearized losses to $v_{t,U}:=g_{t}\,\mathbf{1}\!\left[x_{t}\in U\right]-\min\{0,g_{t}\}\in[0,1]\text{:}$ the shift preserves every difference between experts, and the learner’s mean shifted loss $\mathbb{E}_{U\sim q_{t}}[v_{t,U}]=g_{t}\,p_{t}-\min\{0,g_{t}\}$ is the shift of $g_{t}p_{t}\text{,}$ so with $V_{U}:=\sum_{t}v_{t,U}$ and $\widehat{V}:=\sum_{t}\mathbb{E}_{q_{t}}[v_{t,U}]$ the maximum above equals $\widehat{V}-\min_{U}V_{U}\text{.}$ The weights are the exponential weights of the shifted losses, $w_{t+1}(U):=w_{t}(U)\,e^{-\eta v_{t,U}}$ with $w_{1}\equiv 1\text{,}$ the same posterior as under $g_{t}\mathbf{1}\!\left[x_{t}\in U\right]\text{;}$ the small-loss estimate for losses in $[0,1]$ [Cesa-Bianchi and Lugosi, 2006] then applies. Convexity gives $e^{-\eta v}\leq 1-(1-e^{-\eta})v$ on $[0,1]\text{,}$ so $\log(W_{t+1}/W_{t})\leq-(1-e^{-\eta})\,\mathbb{E}_{q_{t}}[v_{t,U}]\text{;}$ telescoping against $W_{T+1}\geq e^{-\eta V_{U}}\text{,}$ with $\log W_{1}=H_{\mathcal{P}}(1)\text{,}$ and using $1-e^{-\eta}\geq\eta/2$ and $\eta\leq(1+\eta)(1-e^{-\eta})$ for $\eta\in(0,1]\text{,}$

The empty and full upsets bound the best expert: $v_{t,\varnothing}=(-g_{t})_{+}\leq\tau\,\mathbf{1}\!\left[g_{t}<0\right]$ and $v_{t,\mathcal{P}}=(g_{t})_{+}\leq(1-\tau)\,\mathbf{1}\!\left[g_{t}\geq 0\right]\text{,}$ so with $n_{-}$ and $n_{+}$ counting the rounds of either sign,

the last step because the middle expression, under $n_{-}+n_{+}\leq T\text{,}$ is maximized at $\tau n_{-}=(1-\tau)n_{+}\text{.}$ Combining the displays above and evaluating at the chosen $\eta\text{,}$

Lower bound. Let $A\subseteq\mathcal{P}$ be an antichain of size $N_{0}\text{.}$ Any $\{0,1\}$-valued assignment on $A$ extends to a member of $\mathcal{F}_{\mathcal{P}}^{\uparrow}\text{:}$ give each $x$ the largest value assigned on $\{a\in A:a\preceq x\}\text{,}$ with default $0\text{;}$ the extension is isotonic, and on the antichain $A$ it returns the assignment itself. The comparator may therefore choose an endpoint at each point of $A$ independently. The adversary draws every label independently from $\mathrm{Ber}(1-\tau)\text{,}$ a bias at which the pinball Bayes risk is flat:

so every learner’s conditional expected loss is $\rho_{\tau}$ at every round, for a total of $\rho_{\tau}T\text{.}$

If $T<N_{0}\text{,}$ the adversary queries $T$ distinct points of $A$ once each. A single label $y\in\{0,1\}$ at a point is matched by the endpoint $y$ itself at zero cost, so the extension of the pointwise optimal endpoints has zero loss, and $\mathbb{E}[R_{T}]=\rho_{\tau}T\text{.}$ If $T\geq N_{0}\text{,}$ the adversary spreads the $T$ rounds over $A$ as evenly as possible, querying the $i$-th point for $n_{i}\geq\lfloor T/N_{0}\rfloor\geq T/(2N_{0})$ consecutive rounds. With $S_{i}\sim\mathrm{Bin}(n_{i},1-\tau)$ the number of ones observed there, the two endpoint costs at that point are $\tau S_{i}$ and $(1-\tau)(n_{i}-S_{i})\text{,}$ each of mean $\rho_{\tau}n_{i}$ and with difference $S_{i}-(1-\tau)n_{i}\text{,}$ so $\min\{u,v\}=\tfrac{u+v}{2}-\tfrac{|u-v|}{2}$ gives

For $S\sim\mathrm{Bin}(n,\theta)\text{,}$ write $\bar{S}:=S-n\theta$ and $\sigma^{2}:=n\theta(1-\theta)\text{.}$ If $\sigma^{2}\geq 1\text{,}$ Hölder’s inequality $\mathbb{E}\bar{S}^{2}\leq(\mathbb{E}|\bar{S}|)^{2/3}(\mathbb{E}\bar{S}^{4})^{1/3}$ and the fourth-moment bound $\mathbb{E}\bar{S}^{4}\leq 3\sigma^{4}+\sigma^{2}\leq 4\sigma^{4}$ give $\mathbb{E}|\bar{S}|\geq\sigma/2\text{.}$ If $\sigma^{2}<1$ and $\theta\leq\tfrac{1}{2}\text{,}$ then $n\theta\leq 2\sigma^{2}<2\text{,}$ so $\Pr(S=0)=(1-\theta)^{n}\geq e^{-2n\theta}\geq e^{-4}\text{,}$ using $\log(1-\theta)\geq-2\theta$ on $[0,\tfrac{1}{2}]\text{,}$ and $\mathbb{E}|\bar{S}|\geq e^{-4}\,n\theta\geq e^{-4}\sigma^{2}\text{;}$ the case $\theta>\tfrac{1}{2}$ follows by exchanging $S$ with $n-S\text{.}$ In all cases $\mathbb{E}|\bar{S}|\geq e^{-4}\min\{\sigma,\sigma^{2}\}\text{;}$ since $\sigma_{i}^{2}=\rho_{\tau}n_{i}\geq\rho_{\tau}T/(2N_{0})$ and $u\mapsto\min\{\sqrt{u},u\}$ is nondecreasing,

Yao’s principle converts the Bayesian bound into (114).

Grids. On $[m]^{d}\text{,}$ Lemma 61 supplies a rank level of size at least $m^{d-1}/(2d)\text{,}$ an antichain since the rank is strictly monotone, and Lemma 62 at $K=1$ gives $H_{[m]^{d}}(1)=\Theta_{d}(m^{d-1})\text{.}$ The bounds (113) and (114) then match up to factors depending only on $d\text{,}$ uniformly in $\tau\text{,}$ proving the pinball claim. The absolute-loss claim follows by homogeneity: $\lvert\cdot\rvert=2\ell_{1/2}\text{,}$ so $R_{T}^{*}([m]^{d},\lvert\cdot\rvert)=2R_{T}^{*}([m]^{d},\ell_{1/2})\text{,}$ and $\rho_{1/2}=\tfrac{1}{4}$ is absorbed into the constants. ∎

Fix $(x,y)\text{,}$ let $A:=\{r:x\in U_{r}\}$ and $\Delta_{A}:=\sum_{r\in A}d_{r}\text{,}$ so $g_{G}(x)=z_{0}+\Delta_{A}\text{.}$ If $A=\varnothing$ or $A=\{1,\ldots,K\}\text{,}$ the two sides coincide; assume otherwise, so that $z_{0}+\Delta_{A}$ is interior to $[z_{0},z_{K}]$ and the right derivative there is finite. On $[z_{0},z_{K}]$ the convex, finite, continuous $\ell(\cdot,y)$ is the integral of its nondecreasing right derivative $\ell^{\prime}(\cdot,y)\text{,}$ so

while $\ell(g_{G}(x),y)-\ell(z_{0},y)=\int_{E}\ell^{\prime}(u,y)\,du$ with $E:=[z_{0},z_{0}+\Delta_{A}]\text{.}$ The two sets have the same measure $\Delta_{A}\text{,}$ and $E$ is the leftmost subset of $[z_{0},z_{K}]$ of that measure: every point of $E\setminus S_{A}$ is at most $z_{0}+\Delta_{A}$ and every point of $S_{A}\setminus E$ is at least $z_{0}+\Delta_{A}\text{,}$ so the monotonicity of $\ell^{\prime}$ gives

and (a) follows. If $A$ is a prefix $\{1,\ldots,k\}\text{,}$ then $S_{A}=[z_{0},z_{k}]=E$ and the two integrals coincide, which is (b); a nested tuple has a prefix membership vector at every $x\text{.}$ ∎

The two engines, curved case. Fix $K$ and run both engines at rate $\eta$ on the uniform levels $G_{K}\text{.}$ In Algorithm 1, replace the update factor by $e^{-\eta\,\ell(g(j_{t}),y_{t})}\text{:}$ the forward-backward recursion of Section F.1 multiplies per-cell factors into a chain-shaped partition function and is indifferent to which loss generates them. Column-wise comparator enlargement and the proof of Theorem 1 on each chain give, exactly as for the squared loss,

In Algorithm 2, redefine the coefficient $c_{r,t}$ as the loss increment $\ell(r/K,y_{t})-\ell((r-1)/K,y_{t})\text{,}$ with update factor $e^{-\eta c_{r,t}}\text{:}$ the surrogate is additive across layers, so the Gibbs factorization and the per-round equivalence of Section F.2 are unchanged, and each round still costs one call to Lemma 38 per layer; the prediction $\hat{y}_{t}=\tfrac{1}{K}\sum_{r}p_{t,r}$ remains $\mathbb{E}_{\pi_{t}}[g_{G}(x_{t})]$ on the uniform levels. Exp-concavity and Jensen’s inequality give $\ell(\hat{y}_{t},y_{t})\leq-\tfrac{1}{\eta}\log\mathbb{E}_{\pi_{t}}[e^{-\eta\,\ell(g_{G}(x_{t}),y_{t})}]\text{;}$ Lemma 57(a) replaces the loss by the surrogate in the exponent; the layer-additive potential telescopes at cost $\tfrac{1}{\eta}K\log\binom{2m}{m}$ against any tuple; and choosing the nested level sets of $\hat{f}:=q\circ f^{*}$ turns the surrogate back into $\ell(\hat{f}(x_{t}),y_{t})$ by part (b). The rounding cost $L_{T}(\hat{f})-L_{T}(f^{*})\leq\beta T/(8K^{2})$ is the estimate in the proof of Theorem 1. Hence