Proof. Fix \(\varepsilon\in(0,\gamma_u/(2c))\). First note that for any \(h_0\in U_0\) and \(h_1\in U_1\), \[d_\ell(h_0,h_1)\;\ge\;\ell\big(h_0(x_u),h_1(x_u)\big)\;=\;\ell(s_{u,0},s_{u,1})\;=\;\gamma_u.\] Now suppose (towards contradiction) that there exist \(h_0\in U_0\), \(h_1\in U_1\), and \(s\in\mathcal{H}\) such that \(d_\ell(h_0,s)\le \varepsilon\) and \(d_\ell(h_1,s)\le \varepsilon\). By the \(c\)-approximate triangle inequality for \(d_\ell\), \[d_\ell(h_0,h_1)\;\le\;c\big(d_\ell(h_0,s)+d_\ell(h_1,s)\big)\;\le\;2c\varepsilon\;<\;\gamma_u,\] a contradiction. Hence, intuitively, no single center \(s\in\mathcal{H}\) can be within \(\varepsilon\) of both some point in \(U_0\) and some point in \(U_1\). Let \(S\subseteq\mathcal{H}\) be any \(\varepsilon\)-cover of \(U\). Define \[S_b\;:=\;\{s\in S:\;\exists h\in U_b \text{ with } d_\ell(h,s)\le \varepsilon\},\qquad b\in\{0,1\}.\] Then \(S_b\) is an \(\varepsilon\)-cover of \(U_b\), and the previous paragraph implies \(S_0\cap S_1=\emptyset\). Therefore, \[|S|\;\ge\;|S_0|+|S_1|\;\ge\;N(U_0,\varepsilon)+N(U_1,\varepsilon).\] Minimizing over \(\varepsilon\)-covers \(S\) of \(U\) gives the claim. ◻

Proof. Let \(I:=(0,\gamma_u/(2c))\). By Lemma 1, for every \(\varepsilon\in I\) it holds that \[N(U,\varepsilon)\ge N(U_0,\varepsilon)+N(U_1,\varepsilon).\] Hence, for each \(\varepsilon\in I\) there exists \(b\in\{0,1\}\) with \(N(U_b,\varepsilon)\le N(U,\varepsilon)/2\). For \(b\in\{0,1\}\) define the measurable set (because \(\varepsilon\mapsto N(U,\varepsilon)\) is monotone) \[A_b\;:=\;\{\varepsilon\in I:\;N(U_b,\varepsilon)\le N(U,\varepsilon)/2\}.\] Since \(A_0\cup A_1=I\), there exists \(b\) with \(|A_b|\ge |I|/2=\gamma_u/(4c)\), where \(|A_b|\) denotes the Lebesgue measure of \(A_b\). For \(\varepsilon\in A_b\) we have \(\log_2 N(U_b,\varepsilon)\le \log_2 N(U,\varepsilon)-1,\) while for \(\varepsilon\notin A_b\) we have \(\log_2 N(U_b,\varepsilon)\le \log_2 N(U,\varepsilon)\) because \(U_b\subseteq U\) implies \(N(U_b,\varepsilon)\le N(U,\varepsilon)\). Therefore, \[\begin{align} \Phi(U_b) &= \int_{0}^{\operatorname{diam}(\mathcal{H})} \log_2 N(U_b,\varepsilon)\,d\varepsilon \le \int_{0}^{\operatorname{diam}(\mathcal{H})} \log_2 N(U,\varepsilon)\,d\varepsilon- \int_{A_b} 1\,d\varepsilon\\ &= \Phi(U) - |A_b| \le \Phi(U) - \frac{\gamma_u}{4c}. \end{align}\] The above gives the statement of the lemma. ◻

of Theorem 10. Construct a branch \(y\) greedily: start at the root \(y_0\); at each internal node \(y_i\) choose the child \(y_{i+1}\) whose version space satisfies Lemma 2. Then for every \(n\ge 1\), telescoping gives \[\Phi(U_{y_n})\;\le\;\Phi(\mathcal{H})\;-\;\sum_{i=0}^{n-1}\frac{\gamma_{y_i}}{4c}.\] All version spaces along the branch are non-empty by the tree realizability assumption, hence \(\Phi(U_{y_n})\ge 0\). Rearranging yields for all \(n\), \[\sum_{i=0}^{n-1}\gamma_{y_i}\;\le\;4c\,\Phi(\mathcal{H}).\] If the branch is finite, this proves the claim. If it is infinite, letting \(n\to\infty\) (the partial sums are non-decreasing and uniformly bounded) gives \(\sum_{i\ge 0}\gamma_{y_i}\le 4c\,\Phi(\mathcal{H})\). ◻

Proof. By [32], for \(\delta\in(0,1]\), \[N\big(\mathcal{H}_L,\delta;\|\cdot\|_\infty\big) \;\le\; \Big(2\Big\lceil\frac{2\,\operatorname{diam}(\mathcal{X})}{\delta}\Big\rceil+1\Big)^{\,N(\mathcal{X},\delta/(4L))}.\] Here \(\operatorname{diam}(\mathcal{X})=\sup_{x,x'}\|x-x'\|_\infty=2\), and \(\mathcal{X}\) can be covered in \(\|\cdot\|_\infty\) by at most \((\lceil 4L/\delta \rceil)^d\) cubes of side \(\delta/(2L)\), hence \(N(\mathcal{X},\delta/(4L))\le (\lceil 4L/\delta \rceil)^d \leq (8L/\delta)^d\), where the last inequality uses \(L, \frac{1}{\delta} \geq 1\). Taking \(\log_2\) and using \(2\lceil 4/\delta\rceil+1 \le C_0/\delta\) for a universal \(C_0\) yields the claim. ◻

Proof. By Lemma 3 and the identity \(N(\mathcal{H}_L,\varepsilon)=N(\mathcal{H}_L,\varepsilon^{1/q};\|\cdot\|_\infty)\), for \(\varepsilon\in(0,1]\), \[\log_2 N(\mathcal{H}_L,\varepsilon) \;\le\; \Big(\frac{8L}{\varepsilon^{1/q}}\Big)^d\cdot \log_2\Big(\frac{C_0}{\varepsilon^{1/q}}\Big) \;=\; (8^dL^d)\,\varepsilon^{-d/q}\Big(\log_2 C_0+\frac{1}{q}\log_2\frac{1}{\varepsilon}\Big).\] Therefore \[\Phi(\mathcal{H}_L) \;=\;\int_{0}^{1}\log_2 N(\mathcal{H}_L,\varepsilon)\,d\varepsilon \;\le\;8^dL^d\Big(\log_2 C_0\int_0^1 \varepsilon^{-d/q}\,d\varepsilon\;+\;\frac{1}{q}\int_0^1 \varepsilon^{-d/q}\log_2\frac{1}{\varepsilon}\,d\varepsilon\Big).\] Since \(q>d\), we have \(d/q<1\), and both integrals are finite; e.g., \(\int_0^1 \varepsilon^{-d/q}\,d\varepsilon=1/(1-d/q)\) and \(\int_0^1 \varepsilon^{-d/q}\log(1/\varepsilon)\,d\varepsilon= 1/(1-d/q)^2\). This yields \(\Phi(\mathcal{H}_L)\le C_{d,q}L^d\) for an explicit finite \(C_{d,q}\). The bound on \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H}_L)\) follows from 1 and 4 . Finally, [1] gives the stated implication for realizable cumulative loss. ◻

Proof. Fix \(t\) and write the width function \[W_t(x)\;:=\;\overline{h}_t(x)-\underline h_t(x),\qquad w_t:=W_t(x_t).\] Since \(\overline{h}_t\) is a pointwise minimum of \(L\)-Lipschitz functions and \(\underline h_t\) is a pointwise maximum of \(L\)-Lipschitz functions (both clipped to \([0,1]\)), we have that \(W_t\) is \(2L\)-Lipschitz. Realizability implies \(\underline h_t(x)\le f^\star(x)\le \overline{h}_t(x)\) for all \(x\), hence \(y_t=f^\star(x_t)\in[\underline h_t(x_t),\overline{h}_t(x_t)]\) and therefore \[\label{eq:loss-vs-width} |y_t-\hat{y}_t|^q \;\le\;(w_t/2)^q .\tag{5}\]

Let \(\lambda\) denote Lebesgue measure on \(\mathcal{X}\), and define the potential (well-defined since \(q>d\)) \[\Psi_t \;:=\;\int_{\mathcal{X}} W_t(x)^{\,q-d}\,d\lambda(x).\] Since the envelopes tighten, for all \(x\in\mathcal{X}\) we have \(\underline h_{t+1}(x)\ge \underline h_t(x)\) and \(\overline{h}_{t+1}(x)\le \overline{h}_t(x)\), hence \(W_{t+1}(x)\le W_t(x)\). As \(q-d>0\), this implies \(W_{t+1}(x)^{q-d}\le W_t(x)^{q-d}\) and therefore \(\Psi_{t+1}\le \Psi_t\). Set \(r_t:=w_t/(8L)\) and \(B_t:=\{x\in\mathcal{X}:\;\|x-x_t\|_\infty\le r_t\}\). Since \(B_t=\mathcal{X}\cap (x_t+[-r_t,r_t]^d)\), each coordinate interval has length at least \(r_t\), hence \[\lambda(B_t)\;\ge\;r_t^d\;=\;\Big(\frac{w_t}{8L}\Big)^d .\] By \(2L\)-Lipschitzness, for all \(x\in B_t\) we have \(W_t(x)\ge w_t-2Lr_t=(3/4)w_t\). After observing \((x_t,y_t)\), any consistent \(h\in\mathcal{H}_L\) must satisfy \(|h(x)-y_t|\le L\|x-x_t\|_\infty\), hence for all \(x\), \[\overline{h}_{t+1}(x)\le y_t+L\|x-x_t\|_\infty,\qquad \underline h_{t+1}(x)\ge y_t-L\|x-x_t\|_\infty,\] and thus on \(B_t\), \(W_{t+1}(x)\le 2Lr_t=w_t/4\). Consequently, \[\begin{align} \Psi_t-\Psi_{t+1} &\ge \int_{B_t}\Big(W_t(x)^{q-d}-W_{t+1}(x)^{q-d}\Big)\,d\lambda(x)\\ &\ge \lambda(B_t)\Big( (3w_t/4)^{q-d}-(w_t/4)^{q-d}\Big)\\ &\ge \Big(\frac{w_t}{8L}\Big)^d \Big( (3/4)^{q-d}-(1/4)^{q-d}\Big)\,w_t^{q-d} \;=:\;\frac{c_{d,q}}{L^d}\,w_t^q, \end{align}\] where \(c_{d,q}:=8^{-d}\big((3/4)^{q-d}-(1/4)^{q-d}\big)>0\). Summing over \(t\) and using \(\Psi_t\ge 0\) gives \[\sum_{t\ge 1} w_t^q \;\le\;\frac{L^d}{c_{d,q}}\Psi_1.\] At \(t=1\) we have \(\underline h_1\equiv 0\), \(\overline{h}_1\equiv 1\), hence \(W_1\equiv 1\) and \(\Psi_1=\lambda(\mathcal{X})=2^d\). Combining with 5 yields \[\sum_{t\ge 1} |y_t-\hat{y}_t|^q \;\le\;2^{-q}\sum_{t\ge 1} w_t^q \;\le\;2^{-q}\cdot \frac{2^d}{c_{d,q}}\,L^d \;=:\;C'_{d,q}\,L^d.\] The above gives the proof of the lemma. ◻

Proof. Let \(W_t=\overline{h}_t-\underline h_t\) and \(w_t:=W_t(x_t)\). Since \(y_t\in[\underline h_t(x_t),\overline{h}_t(x_t)]\) and \(\hat{y}_t=\tfrac12(\underline h_t(x_t)+\overline{h}_t(x_t))\), we have \(|\hat{y}_t-y_t|\le w_t/2\); hence \(|\hat{y}_t-y_t|>\varepsilon\) implies \(w_t>2\varepsilon\). Fix \(\varepsilon\in(0,1]\) and define \(A_t:=\{x\in\mathcal{X}:\;W_t(x)>\varepsilon\}\). Because the envelopes tighten pointwise, \(W_{t+1}\le W_t\) and thus \(A_{t+1}\subseteq A_t\).

On the event \(w_t>2\varepsilon\), set \(r:=\varepsilon/(4L)\) and \(B_t:=\{x\in\mathcal{X}:\;\|x-x_t\|_\infty\le r\}\). As \(W_t\) is \(2L\)-Lipschitz, for all \(x\in B_t\), \(W_t(x)\ge W_t(x_t)-2Lr>2\varepsilon-\varepsilon/2>\varepsilon\), hence \(B_t\subseteq A_t\). After observing \((x_t,y_t)\), the constraint at time \(t\) implies \(W_{t+1}(x)\le 2L\|x-x_t\|_\infty\le 2Lr=\varepsilon/2\) for all \(x\in B_t\), so \(B_t\cap A_{t+1}=\emptyset\). Therefore \(\lambda(A_t)-\lambda(A_{t+1})\ge \lambda(B_t)\). Since \(\mathcal{X}=[-1,1]^d\), each coordinate interval in \(B_t=\mathcal{X}\cap(x_t+[-r,r]^d)\) has length at least \(r\), hence \(\lambda(B_t)\ge r^d\).

Summing over all \(t\) with \(|\hat{y}_t-y_t|>\varepsilon\) yields \[\#\{t:\;|\hat{y}_t-y_t|>\varepsilon\}\cdot r^d \;\le\;\lambda(A_1)\;\le\;\lambda(\mathcal{X})=2^d,\] so \(\#\{t:\;|\hat{y}_t-y_t|>\varepsilon\}\le 2^d/r^d=(8L/\varepsilon)^d\). Since this holds for every \(\varepsilon>0\), it follows that \(|\hat{y}_t-y_t|\to 0\). ◻

Proof of Corollary 2:. By Corollary 3, \(|\hat{y}_t-y_t|\to 0\). Since \(\ell\) is continuous on the compact set \([0,1]^2\) and vanishes on the diagonal \(\{(y,y):y\in[0,1]\}\), for every \(\varepsilon>0\) there exists \(\delta>0\) such that \(|u-v|<\delta\) implies \(\ell(u,v)<\varepsilon\). Hence \(\ell(\hat{y}_t,y_t)\to 0\). ◻

Proof. Let \(e_t:=|y_t-\hat{y}_t|\in[0,1]\) and for \(\varepsilon\in(0,1]\) write \(N_T(\varepsilon):=\#\{t\le T:\;e_t>\varepsilon\}\). By Corollary 3, \(N_T(\varepsilon)\le \min\{T,(8L/\varepsilon)^d\}\). Using the layer-cake identity, \[\sum_{t=1}^T e_t^d \;=\;d\int_0^1 \varepsilon^{d-1} N_T(\varepsilon)\,d\varepsilon \;\le\;d\int_0^1 \varepsilon^{d-1}\min\{T,(8L/\varepsilon)^d\}\,d\varepsilon .\] Let \(\varepsilon_0:=\min\{1,\,8L\,T^{-1/d}\}\). Then \[\begin{align} \sum_{t=1}^T e_t^d &\le d\int_0^{\varepsilon_0} \varepsilon^{d-1}T\,d\varepsilon \;+\; d\int_{\varepsilon_0}^1 \varepsilon^{d-1}(8L/\varepsilon)^d\,d\varepsilon \\ &= T\varepsilon_0^d \;+\; d(8L)^d\int_{\varepsilon_0}^1 \varepsilon^{-1}\,d\varepsilon \;=\;T\varepsilon_0^d \;+\; d(8L)^d\log(1/\varepsilon_0). \end{align}\] If \(\varepsilon_0=1\), then \(T\le (8L)^d\) and the bound is at most \((8L)^d\). Otherwise \(\varepsilon_0=8L\,T^{-1/d}\), so \(T\varepsilon_0^d=(8L)^d\) and \(\log(1/\varepsilon_0)=\log(T^{1/d}/(8L))\le \frac{1}{d}\log T\) (since \(\varepsilon_0\le 1\)), giving \(\sum_{t=1}^T e_t^d \le (8L)^d(1+\log T)\). ◻

Proof. For \(j\ge 0\) let \(a_j:=2^{-j}/L\) and let \(\mathcal{Q}_j\) be the axis-aligned grid partition of \([-1,1]^d\) into cubes of side \(a_j\) (intersected with \([-1,1]^d\)), so that \(\mathcal{Q}_{j+1}\) refines \(\mathcal{Q}_j\). Let \(M_j:=\lfloor 2/a_j\rfloor^d\) and let \(x_{j,1},\dots,x_{j,M_j}\) be the corresponding cube centers. Set \(\delta_j:=2^{-j-2}\), so \(\sum_{j\ge 0}\delta_j\le 1/2\).

5.4.0.1 Adversary.

Query points level-by-level: \(x_{0,1},\dots,x_{0,M_0}\), then \(x_{1,1},\dots,x_{1,M_1}\), etc., stopping after \(T\) rounds (the last level may be partial). Introduce a root cube \(Q_{-1}:=[-1,1]^d\) and define \(v(Q_{-1})=1/2\). Whenever the adversary queries a center \(x_t\) belonging to a cube \(Q\in\mathcal{Q}_j\) not queried before, after seeing \(\hat{y}_t\) define \[y_t:=v(Q):=v(\mathrm{parent}(Q))+s(Q)\delta_j,\qquad s(Q)\in\{\pm1\},\] where \(\mathrm{parent}(Q)\) is the unique cube in \(\mathcal{Q}_{j-1}\) containing \(Q\) (and \(\mathrm{parent}(Q):=Q_{-1}\) if \(j=0\)). Choose the sign \(s(Q)\) so that \(|\hat{y}_t-y_t|\ge \delta_j/2\) (possible since the two candidates are \(2\delta_j\) apart). Also \(y_t\in[0,1]\) because \(v(Q_{-1})=1/2\) and the total variation along any chain is at most \(\sum_j \delta_j\le 1/2\).

5.4.0.2 Realizability.

Let \(S_T:=\{x_t:t\le T\}\) and define \(y(x_t):=y_t\). If \(x,x'\in S_T\) have least common ancestor at level \(m\), then their increments can differ by at most \(2\delta_k\) per level \(k>m\), hence \[|y(x)-y(x')|\le 2\sum_{k>m}\delta_k = 2^{-m-1}.\] Since they split at level \(m+1\), their centers satisfy \(\|x-x'\|_\infty\ge a_{m+1}=2^{-(m+1)}/L\), so \[|y(x)-y(x')|\le 2^{-m-1}=L a_{m+1}\le L\|x-x'\|_\infty.\] Thus \(y\) is \(L\)-Lipschitz on \(S_T\), and by [33] there is an \(L\)-Lipschitz extension \(\tilde{f}\) to \(\mathcal{X}\). Clipping \(f^\star:=\textrm{clip}_{[0,1]}(\tilde{f})\) keeps the same values on \(S_T\) and preserves \(L\)-Lipschitzness, so \(f^\star\in\mathcal{H}_L\) realizes the sequence.

5.4.0.3 Loss lower bound.

Whenever a fresh level-\(j\) cube is queried we ensured \(|\hat{y}_t-y_t|\ge \delta_j/2\), hence \(|\hat{y}_t-y_t|^d\ge (\delta_j/2)^d = 2^{-d(j+3)}\). Let \(J\) be such that the first \(J\) levels contribute at least one full level, i.e. \[N_J:=\sum_{j=0}^{J-1} M_j \;\le\;T \;<\;N_{J+1}:=\sum_{j=0}^{J} M_j .\] Then the \(N_J\) rounds of fully completed levels yield \[\sum_{t=1}^T |\hat{y}_t-y_t|^d \;\ge\;\sum_{j=0}^{J-1} M_j\,2^{-d(j+3)}.\] Using \(\lfloor 2/a_j\rfloor \ge 2/a_j-1=2^{j+1}L-1\ge 2^jL\) (since \(L\ge 1\)), we have \(M_j\ge (2^jL)^d\), hence each full level contributes at least \(2^{-3d}L^d\), and therefore \[\label{eq:crit-lb-levels} \sum_{t=1}^T |\hat{y}_t-y_t|^d \;\ge\;2^{-3d}L^d\,J.\tag{6}\]

Finally, relate \(J\) and \(T\). If \(J=0\), then all \(T\) rounds are at level \(0\) and \[\sum_{t=1}^T|\hat{y}_t-y_t|^d\ge T(\delta_0/2)^d=2^{-3d}T \ge 2^{-3d}L^d\log(1+T/L^d)\] using \(\log(1+u)\le u\). Assume \(J\ge 1\). Since \(T<N_{J+1}\) and \(M_j\le (2/a_j)^d=(2^{j+1}L)^d\), \[T \;<\;\sum_{j=0}^{J} (2^{j+1}L)^d \;=\;2^d L^d\,\frac{2^{d(J+1)}-1}{2^d-1} \;\le\;C_d\,L^d\,2^{d(J+1)}\] for \(C_d:=\frac{2^d}{2^d-1}\). Hence \[\log\!\Big(1+\frac{T}{L^d}\Big)\;\le\;\log(1+C_d)+d(J+1)\log 2 \;\le\;K_d\,J,\] where \(K_d:=\log(1+C_d)+2d\log 2\) (using \(J+1\le 2J\) for \(J\ge 1\)). Combining with 6 gives the claim with \(c_d:=2^{-3d}/K_d\). ◻

Proof. Let \(m:=\lfloor T^{1/d}\rfloor\) and consider the grid \(G:=\{-1,-1+2/m,\dots,1\}^d.\) Then \(|G|=(m+1)^d\ge T\), and distinct points in \(G\) differ by at least \(2/m\) in \(\|\cdot\|_\infty\). Since \(m\le T^{1/d}\), we have \(2/m\ge 2T^{-1/d}\). Then, any \(T\) distinct points from \(G\) satisfy the claim. ◻

Proof. Fix \(T\ge (2L)^d\) and let \(x_1,\dots,x_T\) be as in Lemma 6, so \(\|x_t-x_s\|_\infty\ge r:=2T^{-1/d}\) for \(t\neq s\). Define \(\Delta:=Lr=2LT^{-1/d}\le 1\) (the last inequality uses \(T\ge (2L)^d\)).

We build a scaled Littlestone tree of depth \(T\) as follows. At depth \(t-1\) we query \(x_t\), and the two outgoing edges are labeled by \(s_{t,0}:=0\) and \(s_{t,1}:=\Delta\). Thus every internal node has gap \(\gamma=\ell_q(0,\Delta)=\Delta^q.\)

It remains to verify realizability of the tree: for every branch \(b\in\{0,1\}^T\), define values on the finite set \(\{x_1,\dots,x_T\}\) by \(f_b(x_t):=b_t\Delta\). For any \(t\neq s\), \[|f_b(x_t)-f_b(x_s)|\;\le\;\Delta\;=\;Lr\;\le\;L\|x_t-x_s\|_\infty,\] By the McShane extension theorem [33], \(f_b\) extends to an \(L\)-Lipschitz function \(\tilde{f}_b:\mathcal{X}\to\mathbb{R}\) satisfying \(\tilde{f}_b(x_t)=f_b(x_t)=b_t\Delta\) for all \(t\). Define \(\hat{f}_b:\mathcal{X}\to[0,1]\) by \(\hat{f}_b(x):=\min\{1,\max\{0,\tilde{f}_b(x)\}\}\). Since clipping is \(1\)-Lipschitz, \(\hat{f}_b\) is still \(L\)-Lipschitz, hence \(\hat{f}_b\in\mathcal{H}_L\), and \(\hat{f}_b(x_t)=b_t\Delta\) for all \(t\). Thus the tree is realizable by \(\mathcal{H}_L\). Along every branch, the sum of gaps equals \(T\Delta^q\), hence \[\inf_{y\in\mathcal{P}(\mathcal{T})}\sum_{i}\gamma_{y_i}\;=\;T\Delta^q\;=\;T(Lr)^q\;=\;T\,(2LT^{-1/d})^q\;=\;(2L)^q\,T^{1-q/d}.\] Taking the supremum over trees in the definition of \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H}_L)\) yields the stated lower bound. Finally, [1] converts this lower bound on \(\mathbb{D}_{\mathrm{onl}}\) into a lower bound on minimax realizable cumulative loss (up to universal constants depending only on \(c\), hence on \(q\)). ◻

Proof. Let \(T:=(2L)^d\). By Lemma 6 there exist \(x_1,\dots,x_T\in[-1,1]^d\) with \(\|x_t-x_s\|_\infty\ge r:=2T^{-1/d}=1/L\) for all \(t\neq s\). Set \(\Delta:=Lr=1\).

Consider the depth-\(T\) scaled Littlestone tree that queries \(x_t\) at depth \(t-1\) and labels the two outgoing edges by \(0\) and \(\Delta\). Each node has gap \(\gamma=\ell_q(0,\Delta)=1\). For any branch \(b\in\{0,1\}^T\), define \(f_b(x_t):=b_t\Delta\in\{0,1\}\). Then for \(t\neq s\), \(|f_b(x_t)-f_b(x_s)|\le 1=\Delta\le L\|x_t-x_s\|_\infty\), so \(f_b\) extends (by McShane and clipping) to some \(h_b\in\mathcal{H}_L\) realizing the branch. Hence the tree is realizable and every root-to-leaf path has total gap \(T\), so \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H}_L)\ge T=(2L)^d\). ◻

Proof. Note that \(\lim_{t \rightarrow \infty} \ell(\hat{y}_t,y_t) = 0\) is equivalent to having for every \(\varepsilon>0\) only finitely many times \(t\) for which \(\ell(\hat{y}_t,y_t) > \varepsilon\). Fix some \(\varepsilon> 0\). Let \(N = N(\mathcal{H},d_{\ell},\varepsilon)\). Since \(\mathcal{H}\) is totally bounded, there exists a finite \(\varepsilon\)-net \(\{f_1,\dots,f_N\}\subseteq \mathcal{H}\) with respect to \(d_{\ell}\), i.e., for every \(f\in\mathcal{H}\) there is an \(i\) such that \(d_\ell(f,f_i)\le \varepsilon\). Select such representatives \(\{f_i\}_{i=1}^N\). Upon receiving \(x_t\), pick any index \(i\) not yet eliminated and predict \(\hat{y_t}:=f_i(x_t)\); if \(\ell(\hat{y}_t,y_t) > \varepsilon\), then eliminate \(f_i\) (and never use it again).

Let \(f^\star\in\mathcal{H}\) realize the sequence, i.e., \(y_t=f^\star(x_t)\) for all \(t\), and let \(i^\star\) satisfy \(d_\ell(f^\star,f_{i^\star})\le \varepsilon\). Then for all \(t\), \[\ell\bigl(f_{i^\star}(x_t),y_t\bigr) =\ell\bigl(f_{i^\star}(x_t),f^\star(x_t)\bigr) \le d_\ell(f_{i^\star},f^\star)\le \varepsilon,\] so \(f_{i^\star}\) is never eliminated. Each time \(\ell(\hat{y}_t,y_t)>\varepsilon\) occurs, we eliminate one representative, hence this can happen at most \(N-1\) times. Since this holds for every \(\varepsilon>0\), applying the argument for a sequence \(\varepsilon=1,1/2,1/3,\dots\) implies \(\ell(\hat{y}_t,y_t)\to 0\). ◻

A Second Proof of Corollary 2. Fix \(\varepsilon>0\). Since \(\ell\) is continuous on the compact set \([0,1]^2\), it is uniformly continuous; moreover, as \(\ell(y,y)=0\) for all \(y\), there exists \(\delta=\delta(\varepsilon)>0\) such that for all \(a,b\in[0,1]\), \[|a-b|\le \delta \;\Longrightarrow\;\ell(a,b)\le \varepsilon.\] Hence, for any \(f,g\in\mathcal{H}_L\), if \(\|f-g\|_\infty\le \delta\) then \[d_\ell(f,g)=\sup_{x}\ell(f(x),g(x))\le \varepsilon.\] On the other hand, \((\mathcal{H}_L,\|\cdot\|_\infty)\) is totally bounded (indeed compact) by Arzelà–Ascoli, since \([-1,1]^d\) is compact and \(\mathcal{H}_L\) is uniformly bounded and equicontinuous (uniformly \(L\)-Lipschitz). Therefore, there exists a finite \(\delta\)-net of \(\mathcal{H}_L\) in \(\|\cdot\|_\infty\), which is an \(\varepsilon\)-net in \(d_\ell\). Thus \(\mathcal{H}_L\) is totally bounded w.r.t.\(d_\ell\), and the theorem applies to give a deterministic proper algorithm with only finitely many rounds where \(\ell(\hat{y}_t,y_t)>\varepsilon\). Since this holds for every \(\varepsilon>0\), we conclude \(\ell(\hat{y}_t,y_t)\to 0\). ◻

Proof. Define the potential function \(\phi_t = \| w_t - w\|^2\) for every \(1 \leq t \leq T + 1\). Fix some \(1 \leq t \leq T\); then, \[\begin{align} \label{eq:1} \phi_{t+1} &= \|w_{t+1} - w\|^2 \\ &= \|w_t - \alpha_t \cdot x_t - w\|^2 \\ &= \|(w_t - w) - \alpha_t \cdot x_t\|^2\\ &= \|(w_t - w)\|^2 - 2 (w_t - w) \cdot (\alpha_t x_t) + \| \alpha_t x_t \|^2\\ &= \phi_t - 2 (w_t - w) \cdot (\alpha_t x_t) + \| \alpha_t x_t \|^2\\ &= \phi_t - 2 \alpha_t (w_t - w) \cdot x_t + \alpha^2_t \| x_t \|^2\\ \end{align}\tag{7}\]

By Claim 15 and the equation above it follows that: \[\phi_{t+1} \leq \phi_t - 2 \alpha^2_t + \alpha^2_t \| x_t \|^2\] Observe that \[\begin{align} \ell_t = \| \textrm{ReLU}(w_t \cdot x_t) - \textrm{ReLU}(w \cdot x_t)\|^2 = \left(\textrm{ReLU}(w_t \cdot x_t) - \textrm{ReLU}(w \cdot x_t)\right)^2=\alpha^2_t. \end{align}\]

Thus, \(\ell_t = \alpha^2_t\) and by combining the above \[\phi_{t+1} \leq \phi_t - 2 \alpha^2_t + \alpha^2_t \| x_t \|^2 \leq \phi_t - 2 \alpha^2_t + \alpha^2_t = \phi_t - \alpha^2_t = \phi_t -{\ell_t}.\] The second inequality follows from the assumption \(\|x_t\| \leq 1\). The above equation gives \({\ell_t} \leq \phi_t - \phi_{t+1}\). Therefore, \[\begin{align} L &= \sum_{1 \leq t \leq T} \ell_t \\ &\leq \sum_{1 \leq t \leq T} \left(\phi_t - \phi_{t+1}\right) \\ &= \left(\phi_1 - \phi_{2}\right) + \left(\phi_2 - \phi_{3}\right) + \ldots + \left(\phi_{T-1} - \phi_{T}\right) + \left(\phi_T - \phi_{T+1}\right) \\ &= \phi_{1} - \phi_{T+1} \\ &\leq \phi_{1}\\ &= \|w\|^2\\ & \leq 1.\\ \end{align}\] The last inequality follows from the assumption \(\|w\| \leq 1\). ◻

Proof. It is enough to prove the claim for even \(k\). If \(k\) is odd, ignore one ReLU and apply the even case to \(k-1\), which changes the lower bound only by a universal constant. Assume therefore that \(k\) is even.

First assume that \(d\) is a power of two. For each sign vector \(s=(s_1,\ldots,s_d)\in\{\pm1\}^d\), let \(v_s=s/\sqrt d\), and define \[h_s(x)=\textrm{clip}\left(\frac{k}{2}|\langle v_s,x\rangle|\right).\] Then \(h_s\in\mathcal{H}_{k,d}\), since \[\frac{k}{2}|\langle v_s,x\rangle| = \sum_{\ell=1}^{k/2} \left( \textrm{ReLU}(\langle v_s,x\rangle)+\textrm{ReLU}(\langle -v_s,x\rangle) \right).\] This uses exactly \(k\) ReLUs, all input weights have norm \(1\), and all output weights are \(1\).

The adversary maintains a partition of \([d]=\{1,\ldots,d\}\) into dyadic intervals. Initially the partition consists of the singleton intervals \(\{1\},\ldots,\{d\}\). At later stages, the adversary only merges two adjacent dyadic intervals of the same size. For a block \(B\subseteq[d]\) and a sign vector \(s\in\{\pm1\}^d\), write \(s_B=(s_i)_{i\in B}\in\{\pm1\}^B\) for the restriction of \(s\) to the coordinates in \(B\). Each current block \(B\) has a public reference pattern \(r_B\in\{\pm1\}^B\). The invariant is that the surviving signs are exactly those \(s\in\{\pm1\}^d\) such that, for every current block \(B\), one has \(s_B=r_B\) or \(s_B=-r_B\). Initially, set \(r_{\{i\}}(i)=1\) for every singleton block \(\{i\}\), so all signs survive and the invariant holds. The reference patterns are determined by the past transcript and may be revealed to the learner; the only hidden information is whether \(s_B=r_B\) or \(s_B=-r_B\) on each current block \(B\).

Consider a merge of two adjacent current blocks \(B_0,B_1\), each of size \(m/2\), and write \(B=B_0\cup B_1\), so \(|B|=m\). The adversary queries \[x_B = \frac{1}{\sqrt m} \left( \sum_{i\in B_0}r_{B_0}(i)e_i + \sum_{i\in B_1}r_{B_1}(i)e_i \right),\] where \(e_1,\ldots,e_d\) are the standard basis vectors. This is a valid input because \[\|x_B\|_2^2 = \frac{1}{m}\left(|B_0|+|B_1|\right) = 1.\]

By the invariant, before the label is chosen, both orientations of each child block are feasible independently. If the two child blocks have the same orientation, meaning either \(s_{B_0}=r_{B_0}\) and \(s_{B_1}=r_{B_1}\), or \(s_{B_0}=-r_{B_0}\) and \(s_{B_1}=-r_{B_1}\), then \[|\langle v_s,x_B\rangle| = \frac{|B_0|+|B_1|}{\sqrt{dm}} = \sqrt{\frac{m}{d}}.\] If the two child blocks have opposite orientations, meaning either \(s_{B_0}=r_{B_0}\) and \(s_{B_1}=-r_{B_1}\), or \(s_{B_0}=-r_{B_0}\) and \(s_{B_1}=r_{B_1}\), then \[|\langle v_s,x_B\rangle| = \frac{\bigl||B_0|-|B_1|\bigr|}{\sqrt{dm}} = 0.\] Thus the two labels \[0 \qquad\text{and}\qquad \alpha_m=\min\left\{\frac{k}{2}\sqrt{\frac{m}{d}},1\right\}\] are both realizable by surviving hypotheses.

For every prediction \(\widehat y\), one of the two labels \(0,\alpha_m\) causes square loss at least \(\alpha_m^2/4\). Otherwise both \(|\widehat y|\) and \(|\widehat y-\alpha_m|\) would be smaller than \(\alpha_m/2\), contradicting \(|\alpha_m|\le |\widehat y|+|\widehat y-\alpha_m|\). Hence, on every level with \(m\le 4d/k^2\), no clipping occurs, and each merge forces loss at least \(k^2m/(16d)\).

After the label is chosen, the adversary updates the merged block \(B\). If it chooses the high label \(\alpha_m\), it keeps exactly the surviving signs with the same orientation and defines the new reference pattern by \[r_B(i)= \begin{cases} r_{B_0}(i), & i\in B_0,\\ r_{B_1}(i), & i\in B_1. \end{cases}\] If it chooses the zero label, it keeps exactly the surviving signs with opposite orientations and defines \[r_B(i)= \begin{cases} r_{B_0}(i), & i\in B_0,\\ -r_{B_1}(i), & i\in B_1. \end{cases}\] In both cases, the surviving restrictions on the merged block \(B\) are exactly \(r_B\) and \(-r_B\). All other blocks and reference patterns are unchanged. Therefore the invariant is preserved, and the surviving set remains nonempty.

The adversary performs all merges bottom-up: first it merges singleton blocks into blocks of size \(2\), then blocks of size \(2\) into blocks of size \(4\), and so on. At a level whose merged block size is \(m\), there are \(d/m\) merges. Therefore every level with \(m\le 4d/k^2\) contributes loss at least \[\frac{d}{m}\cdot\frac{k^2m}{16d} = \frac{k^2}{16}.\] The dyadic levels are \(m=2,4,\ldots,d\). The condition \(m\le 4d/k^2\) holds for \(\Omega(\log(d/k^2))\) of these levels whenever \(d/k^2\to\infty\). Thus the total forced loss is \(\Omega(k^2\log(d/k^2))\). For fixed \(k\), this is \(\Omega(k^2\log d)\).

The construction uses exactly \(d-1\) queries and is realizable. Indeed, along every path, the invariant keeps at least one sign vector alive. Choosing any final surviving \(s\), the fixed hypothesis \(h_s\in\mathcal{H}_{k,d}\) agrees with all revealed labels on that path.

Now consider general \(d\). Let \(D=2^{\lfloor \log_2 d\rfloor}\). Run the same construction on the first \(D\) coordinates, and set all other coordinates to zero in both the queries and the vectors \(v_s\). Equivalently, use sign vectors \(s\in\{\pm1\}^D\) and vectors \[v_s=\frac{1}{\sqrt D}(s_1,\ldots,s_D,0,\ldots,0)\in\mathbb{R}^d.\] The proof above gives a lower bound of \(\Omega(k^2\log(D/k^2))\) using \(D-1\) queries. Since \(D\ge d/2\), this is \(\Omega(k^2\log(d/k^2))\) whenever \(d/k^2\to\infty\). Also \(D-1\le d-1\le T\), so the construction fits the stated horizon. ◻

Proof. Let \(u:=(a-b)^2/4\), \(v:=(a-c)^2/4\), \(w:=(c-b)^2/4\). Then \(u\le 2(v+w)\) (the standard \(2\)-approximate triangle for squared loss). We show \(\min\{1,u\}\le 2(\min\{1,v\}+\min\{1,w\})\). If \(\max\{v,w\}\ge 1\), then the RHS is at least \(2\) and the claim holds since the LHS is at most \(1\). Otherwise \(v<1\) and \(w<1\), hence \(\min\{1,v\}=v\) and \(\min\{1,w\}=w\), so \(\min\{1,u\}\le u\le 2(v+w)=2(\min\{1,v\}+\min\{1,w\})\). ◻

Proof. Let \(m:=\mathop{\mathrm{fat}}_\alpha(\mathcal{V})\) and assume for contradiction that both children have \(\mathop{\mathrm{fat}}_\alpha\) dimension at least \(m\). Without loss of generality assume \(a>b\) (otherwise swap the roles of \(\mathcal{V}_0\) and \(\mathcal{V}_1\)). Glue depth-\(m\) \(\alpha\)-shattering trees for \(\mathcal{V}_0\) and \(\mathcal{V}_1\) under a new root at instance \(x\) with threshold \(\theta:=(a+b)/2\), attaching the \(\mathcal{V}_0\) subtree to the branch requiring \(f(x)\ge \theta+\alpha\) and the \(\mathcal{V}_1\) subtree to the branch requiring \(f(x)\le \theta-\alpha\). Since \(\Delta=a-b\ge 2\alpha\), we have \(a\ge \theta+\alpha\) and \(b\le \theta-\alpha\), yielding an \(\alpha\)-shattering tree of depth \(m+1\) for \(\mathcal{V}\), a contradiction. ◻

Proof. For a node \(u\), let \(\mathcal{V}(u)\subseteq\mathcal{H}\) be its version space (hypotheses consistent with the root-to-\(u\) labels), and define the truncated potential \[\Psi(u)\;:=\;16\sum_{r=-1}^{K}\alpha_r^2\,\mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{V}(u)).\] Construct a branch top-down. At an internal node \(u\):

• If \(\Delta_u\le 1/\sqrt d\), move to an arbitrary child.

• If \(\Delta_u>1/\sqrt d\), choose the unique \(r\in\{-1,0,\dots,K\}\) such that \[2\alpha_r < \Delta_u \le 4\alpha_r.\] We justify existence as follows. Since \(4\alpha_{-1}=2\) and always \(\Delta_u\le 2\) (labels lie in \([-1,1]\)), and also \(\Delta_u>1/\sqrt d\ge 2^{-K}\) with \(4\alpha_K=2^{-K}\), such \(r\le K\) exists. Apply Lemma 8 at scale \(\alpha_r\) to \(\mathcal{V}(u)\); since \(\Delta_u\ge 2\alpha_r\), there exists a child \(u^+\) with \(\mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{V}(u^+))\le \mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{V}(u))-1\). Move to such a child \(u^+\).

Along the resulting branch \(P\), whenever we visit a node \(u\) with \(\Delta_u>1/\sqrt d\) and bucket index \(r\), the potential drops by at least \(16\alpha_r^2\), and also \(\Delta_u^2\le (4\alpha_r)^2=16\alpha_r^2\). Thus, \[\sum_{u\in P:\Delta_u>1/\sqrt d}\Delta_u^2 \;\le\; \sum_{u\in P:\Delta_u>1/\sqrt d}\big(\Psi(u)-\Psi(u^+)\big) \;\le\; \Psi(\text{root}) \;=\; 16\sum_{r=-1}^{K}\alpha_r^2\,\mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{H}).\] Note that the argument only used the forced choice at nodes with \(\Delta_u>1/\sqrt d\); at nodes with \(\Delta_u\le 1/\sqrt d\) the child was arbitrary. Therefore, the same bound holds for any branch that, whenever it reaches a node with \(\Delta_u>1/\sqrt d\), follows the \(\alpha_r\)-decreasing child chosen in the construction. ◻

Proof. We invoke the standard sequential Rademacher–fat chain from [5].

7.3.0.1 Step 1 (linear class).

Let \(\mathcal{G}:=\{x\mapsto \langle w,x\rangle:\;\|w\|_2\le 1\}\subseteq[-1,1]^{\mathcal{X}}\). By [5], for all \(T\ge 1\), \[\mathfrak{R}_T(\mathcal{G})\;\le\;\frac{C_0}{\sqrt{T}}\] for a universal constant \(C_0\).

7.3.0.2 Step 2 (single ReLU with a scalar).

Let \[\mathcal{R}:=\{x\mapsto a\,\textrm{ReLU}(\langle w,x\rangle):\;|a|\le 1,\;\|w\|_2\le 1\}.\] Since \(\textrm{ReLU}\) is \(1\)-Lipschitz, by [5] there is a factor \(\rho(T)=O(\log^{3/2}(eT))\) such that \[\mathfrak{R}_T(\mathcal{R})\;\le\;8\,\rho(T)\,\mathfrak{R}_T(\mathcal{G})\;\le\;\frac{C_1\,\rho(T)}{\sqrt{T}}\] for a universal constant \(C_1\).

7.3.0.3 Step 3 (unclipped \(k\)-term sums and clipping).

Let \[\mathcal{H}_0:=\Bigl\{x\mapsto \sum_{j=1}^k r_j(x):\;r_j\in\mathcal{R}\Bigr\}.\] For any \(\mathcal{X}\)-valued tree \(z\), separability of the parameters across \(j\) gives \[\mathfrak{R}_T(\mathcal{H}_0,z) =\frac{1}{T}\,\mathbb{E}_\varepsilon\Bigl[\sup_{r_1,\dots,r_k\in\mathcal{R}}\sum_{j=1}^k\sum_{t=1}^T \varepsilon_t r_j(z_t(\varepsilon))\Bigr] =\sum_{j=1}^k \mathfrak{R}_T(\mathcal{R},z) = k\,\mathfrak{R}_T(\mathcal{R},z).\] Hence \(\mathfrak{R}_T(\mathcal{H}_0)\le k\,\mathfrak{R}_T(\mathcal{R})\le C_1 k\rho(T)/\sqrt{T}\). Now \(\mathcal{H}\) is obtained by clipping \(\mathcal{H}_0\) pointwise to \([-1,1]\) (i.e., applying \(\textrm{clip}\)), and \(\textrm{clip}\) is \(1\)-Lipschitz on \(\mathbb{R}\), so by contraction [5], \[\mathfrak{R}_T(\mathcal{H})\;\le\;\mathfrak{R}_T(\mathcal{H}_0)\;\le\;\frac{C_1 k\rho(T)}{\sqrt{T}}.\]

7.3.0.4 Step 4 (fat from sequential Rademacher).

By [5], for all \(\alpha\in(0,1]\), \[\alpha\sqrt{\frac{\min\{\mathop{\mathrm{fat}}_\alpha(\mathcal{H}),T\}}{T}} \;\le\;C_2\,\mathfrak{R}_T(\mathcal{H}) \;\le\;\frac{C_3\,k\rho(T)}{\sqrt{T}}\] for universal constants \(C_2,C_3\). Choosing \(T=\Theta\!\big(\alpha^{-2}k^2\log^3(ek/\alpha)\big)\) large enough ensures \[C_3 k\rho(T)/\sqrt{T}<\alpha/2,\] which forces \(\mathop{\mathrm{fat}}_\alpha(\mathcal{H})<T\) and yields the claim. ◻

Proof. By Proposition 16, \(\alpha_r^2\mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{H})\le Ck^2\log^3(ek/\alpha_r)\). Since \(\alpha_r=2^{-(r+2)}\), \(\log(ek/\alpha_r)=\Theta(\log(ek)+r+1)\) and \(\sum_{r\le K}(\log(ek)+r+1)^3=O((\log(ek)+K)^4)=O(\log^4(edk))\). ◻

Proof. Run the above rule, but leave the choices at nodes with \(\Delta_u\le 1/\sqrt d\) unspecified. This induces a full binary tree \(S\) whose internal nodes are exactly the reached nodes with \(\Delta_u\le 1/\sqrt d\) (choices only occur there), with the same queried instances and the same two edge-labels \(s_{u,0},s_{u,1}\) as in \(T\) at those nodes. If needed, we pad shorter branches with dummy nodes of zero gap (same label on both edges), which preserves shattering and does not change branch energies, yielding a full binary tree of uniform depth. Because \(T\) is shattered by \(\mathcal{H}\), every branch of \(S\) corresponds to a branch of \(T\) (obtained by inserting the forced moves at \(\Delta_u>1/\sqrt d\)), hence is realizable by some hypothesis in \(\mathcal{H}\). Therefore \(S\) is shattered by \(\mathcal{H}\). Now scale all edge-labels in \(S\) by \(\sqrt d\) to obtain a tree \(S'\) with labels \(s'_{u,b}:=\sqrt d\,s_{u,b}\). For every branch of \(S\), if \(h_b\in\mathcal{H}\) realizes it, then the scaled function \(g_b:=\sqrt d\,h_b\) lies in \(\mathcal{F}\) and realizes the corresponding branch of \(S'\). Thus \(S'\) is shattered by \(\mathcal{F}\).

For every node \(u\) of \(S\) we have \(\Delta_u\le 1/\sqrt d\), hence in \(S'\) the gap is \(\Delta'_u=\sqrt d\,\Delta_u\le 1\) and clipping in \(\ell_\cap\) does not occur: \[\ell_{\cap}(s'_{u,0},s'_{u,1})=(\Delta'_u)^2/4=d\,\Delta_u^2/4.\] Therefore, for every branch \(b\) of \(S'\), \[E_{S'}(b)=\frac{d}{4}\sum_{u\in b}\Delta_u^2=\frac{d}{4}\cdot E_{\mathrm{small}}(P_b),\] where \(P_b\) is the corresponding branch of \(T\) produced by the rule. Hence \[\inf_b E_{S'}(b)=\frac{d}{4}\cdot \inf_b E_{\mathrm{small}}(P_b).\] Since \(S'\) is a valid shattered tree for \(\mathcal{F}\), by definition of \(\mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap})\), \[\mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap})\;\ge\;\inf_b E_{S'}(b)\;=\;\frac{d}{4}\cdot \inf_b E_{\mathrm{small}}(P_b).\] Choose a branch \(b^*\) attaining the infimum. The corresponding branch \(P:=P_{b^*}\) of \(T\) follows the large-gap rule by construction and satisfies \(E_{\mathrm{small}}(P)\le \frac{4}{d}\mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap})\). ◻

Proof. Since \(\textrm{clip}\) is \(1\)-Lipschitz and \(|\textrm{ReLU}(u)-\textrm{ReLU}(v)|\le |u-v|\), for any \(x\in\mathcal{X}\) we have \[\begin{align} |h_\theta(x)-h_{\theta'}(x)| &\le \sum_{j=1}^k \big|a_j\,\textrm{ReLU}( w^j \cdot x)-a_j'\,\textrm{ReLU}(w^{j\prime} \cdot x)\big|\\ &\le \sum_{j=1}^k \Big(|a_j-a_j'|\cdot|\textrm{ReLU}(w^j \cdot x)|\;+\;|a_j'|\cdot|\textrm{ReLU}( w^j \cdot x)-\textrm{ReLU}(w^{j\prime} \cdot x)|\Big)\\ &\le \sum_{j=1}^k \Big(|a_j-a_j'|\;+\;|\langle w^j-w^{j\prime},x\rangle|\Big) \;\le\; \sum_{j=1}^k \Big(|a_j-a_j'|\;+\;\|w^j-w^{j\prime}\|_2\Big), \end{align}\] using \(\textrm{ReLU}(w^j \cdot x)\in[0,1]\) and \(|a_j'|\le 1\). By Cauchy–Schwarz, \[\sum_{j=1}^k |a_j-a_j'|\;\le\;\sqrt{k}\,\|a-a'\|_2, \qquad \sum_{j=1}^k \|w^j-w^{j\prime}\|_2\;\le\;\sqrt{k}\,\|w-w'\|_2,\] hence \(\sup_x |h_\theta(x)-h_{\theta'}(x)|\le \sqrt{2k}\,\|\theta-\theta'\|_2\). Multiplying by \(\sqrt d\) gives the first inequality. For the second, use \(\ell_\cap(u,v)\le (u-v)^2/4\) and take \(\sup_{x\in\mathcal{X}}\). ◻

Proof. Note that \(\Theta\subseteq B_2^{k(d+1)}(0,\sqrt{2k})\). A standard volumetric bound for Euclidean balls [34] gives \(N(B_2^{k(d+1)}(0,\sqrt{2k}),r)\le (3\sqrt{2k}/r)^{k(d+1)}\) for \(r\in(0,1]\). ◻

Proof. By Lemma 12, \(d_{\ell_{\cap}}(g_\theta,g_{\theta'})\le \min\{1,(L\|\theta-\theta'\|_2)^2\}\) with \(L:=\sqrt{kd/2}\). Thus, for \(\varepsilon\in(0,1]\), an \(\varepsilon\)-cover in \(d_{\ell_\cap}\) is induced by an \(r:=\min\{1,\sqrt{\varepsilon}/L\}\) cover in \(\|\cdot\|_2\), so \[N(\mathcal{F},\varepsilon)\;\le\;N(\Theta,r;\|\cdot\|_2).\] By Lemma 13, \[N(\mathcal{F},\varepsilon)\;\le\;\Big(\frac{3\sqrt{2k}}{r}\Big)^{k(d+1)} =\Big(3\sqrt{2k}\,\max\{1,L/\sqrt\varepsilon\}\Big)^{k(d+1)} \le \Big(\frac{3\sqrt{2k}\,(1+L)}{\sqrt\varepsilon}\Big)^{k(d+1)}, \qquad(\varepsilon\in(0,1]).\] Recall the entropy potential \(\Phi(\mathcal{F}):=\int_0^1 \log_2 N(\mathcal{F},\varepsilon)\,d\varepsilon\). Then \[\log_2 N(\mathcal{F},\varepsilon)\;\le\;k(d+1)\log_2\!\big(3\sqrt{2k}\,(1+L)\big)\;+\;\frac{k(d+1)}{2}\log_2(1/\varepsilon),\] so using \(\int_0^1 \log_2(1/\varepsilon)\,d\varepsilon=1/\ln 2\), \[\Phi(\mathcal{F})\;\le\;k(d+1)\log_2\!\big(3\sqrt{2k}\,(1+L)\big)\;+\;\frac{k(d+1)}{2\ln 2} \;=\;O\big(kd\log d\big).\] Finally, since \(\ell_{\cap}\) is a \(2\)-approximate pseudo-metric (Lemma 7), the standard entropy-potential branch argument yields \(\mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap})\le 8\,\Phi(\mathcal{F})=O(kd\log d)\). ◻

Proof. Fix any scaled Littlestone tree \(T\) shattered by \(\mathcal{H}\). Apply Lemma 11 to obtain a branch \(P\) that follows the large-gap fat-shattering-drop rule at every node with \(\Delta_u>1/\sqrt d\) and satisfies \(\sum_{u\in P:\Delta_u\le 1/\sqrt d}\Delta_u^2 \le \frac{4}{d} \mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap})\). For this same branch \(P\), the large-gap bound from Lemma 9 applies (because \(P\) follows the required rule at every large-gap node), yielding \[\sum_{u\in P:\Delta_u>1/\sqrt d}\Delta_u^2 \;\le\;16\sum_{r=-1}^{K}\alpha_r^2\,\mathop{\mathrm{fat}}_{\alpha_r}(\mathcal{H}) \;=\;O(k^2\log^4 d),\] where the last step uses Lemma 10. For the remaining nodes on \(P\) with \(\Delta_u\le 1/\sqrt d\), Proposition 17 gives \[\sum_{u\in P:\;\Delta_u\le 1/\sqrt d}\Delta_u^2 \;\le\; \frac{4}{d}\,\mathbb{D}_{\mathrm{onl}}(\mathcal{F};\ell_{\cap}) \;=\;O(k\log d).\] Summing the two contributions yields \(\sum_{u\in P}\Delta_u^2=O(k^2\log^4 d)\). Since on shattered trees for \(\mathcal{H}\subseteq[-1,1]^{\mathcal{X}}\) we have \(\ell_{\cap}(s_{u,0},s_{u,1})=\Delta_u^2/4\), it follows that \(E_T(P)=\sum_{u\in P}\ell_{\cap}(s_{u,0},s_{u,1})=O(k^2\log^4 d)\), hence \(\inf_b E_T(b)\le O(k^2\log^4 d)\). Taking \(\sup_T\) gives \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H};\ell_{\cap})\le O(k^2\log^4 d)\).

Finally, for realizable squared loss with labels in \([-1,1]\), one may clip the learner’s predictions to \([-1,1]\) without increasing squared loss, and on \([-1,1]\) we have squared loss equals to four times the loss \(\ell_{\cap}\). Thus, the minimax realizable deterministic cumulative squared loss is at most \(4\,\mathbb{D}_{\mathrm{onl}}(\mathcal{H};\ell_{\cap})=O(k^2\log^4 d)\). This gives the proof of the theorem. ◻

Proof. We repeat the large-gap/small-gap decomposition with threshold \(1/\sqrt d\).

8.0.0.1 Large gaps.

The proof of Lemma 9 is purely combinatorial, so it immediately applies: for any shattered tree, along a branch that follows the decreasing-child rule at large-gap nodes, \[\sum_{\Delta_u>1/\sqrt d}\Delta_u^2 \;\le\; 16\sum_{r=-1}^{K}\alpha_r^2\,\mathop{\mathrm{fat}}_{\alpha_r}\!\big(\mathcal{H}_{L,k,d}^{\mathrm{deep}}\big), \qquad K=\lceil \log_2(\sqrt d)\rceil.\] It suffices to bound \(\mathop{\mathrm{fat}}_\alpha\!\big(\mathcal{H}_{L,k,d}^{\mathrm{deep}}\big)\). We do so via the sequential Rademacher complexity, using a vector Rademacher peeling argument that exploits the row independence of the weight matrices.

Vector Rademacher recursion. For a class of vector-valued functions \(\mathcal{V}\subseteq(\mathbb{R}^k)^{\mathcal{X}}\) and a sequential tree \(z=(z_t)_{t=1}^T\) of depth \(T\) (i.e., each \(z_t:\{\pm1\}^{t-1}\to\mathcal{X}\) and \(z_t(\varepsilon)\) denotes \(z_t(\varepsilon_1,\ldots,\varepsilon_{t-1})\)), define \[\mathfrak{R}^{\mathrm{vec}}_T(\mathcal{V}) \;:=\; \frac{1}{T}\, \mathbb{E}_\varepsilon\!\Big[\sup_{v\in\mathcal{V}}\,\Big\|\sum_{t=1}^T \varepsilon_t\, v(z_t(\varepsilon))\Big\|_2\Big]\] where \(\varepsilon_1,\ldots,\varepsilon_T \sim \mathrm{Unif}\{\pm 1\}\) independently.

Let \(\mathcal{V}_\ell\) (\(\ell=1,\dots,L-1\)) denote the class of layer-\(\ell\) activation vectors \(z^{(\ell)}:\mathcal{X}\to\mathbb{R}^k\) (ranging over all admissible weight and bias choices at layers \(1,\dots,\ell\)). We prove:

where \(\rho(T)=O(\log^{3/2}(eT))\) is the sequential contraction overhead from [5].

Normalization for Cor. 5. Corollary 5 in [5] is stated for classes \(G\subseteq[-1,1]^{\mathcal{Z}}\). If \(G\subseteq\mathbb{R}^{\mathcal{Z}}\) satisfies \(\sup_{g\in G,z\in\mathcal{Z}}|g(z)|\le B<\infty\), define \(\bar G:=\{g/B:\;g\in G\}\subseteq[-1,1]^{\mathcal{Z}}\) and \(\phi_B(u,z):=\phi(Bu,z)\). Then \(\phi_B(\cdot,z)\) is \((B \lambda)\)-Lipschitz whenever \(\phi(\cdot,z)\) is \(\lambda\)-Lipschitz, and by Lemma 3 and Cor. 5 of [5] we have, whenever \(\mathfrak{R}_T(\bar G)\ge 1/T\), \[\label{eq:cor5-normalized} \mathfrak{R}_T(\phi\circ G)=\mathfrak{R}_T(\phi_B\circ \bar G)\;\le\;\rho(T)\,\lambda\cdot \mathfrak{R}_T(G).\tag{9}\] In our applications \(G\) is symmetric and contains the constants \(\pm 1\) (via the bias), hence \(\mathfrak{R}_T(\bar G)\ge c/(B\sqrt{T})\) for a universal constant \(c>0\), so the condition \(\mathfrak{R}_T(\bar G)\ge 1/T\) holds for all \(T\ge c^{-2}B^2\), which is satisfied by the choices of \(T\) used below.

Base case. For layer \(1\), the same argument gives \[\mathfrak{R}^{\mathrm{vec}}_T(\mathcal{V}_1) \;=\; O\!\left(\frac{\sqrt{k}\,\rho(T)}{\sqrt{T}}\right).\]

Unrolling the recursion. By induction, using 8 for \(\ell=2,\dots,L-1\) and the base case: \[\mathfrak{R}^{\mathrm{vec}}_T(\mathcal{V}_{L-1}) \;\le\; \frac{C_L\,(\sqrt{k})^{L-1}\rho(T)^{L-1}}{\sqrt T}.\] Let \(\mathcal{G}\) be the pre-clipped scalar class \(\mathcal{G}:=\{x\mapsto \langle a,z^{(L-1)}(x)\rangle+c:\;a\in[-1,1]^k,\;c\in[-1,1]\}\). Since \(\textrm{clip}\) is \(1\)-Lipschitz, applying 9 to \(\textrm{clip}\circ \mathcal{G}\) yields \[\mathfrak{R}_T\!\big(\mathcal{H}_{L,k,d}^{\mathrm{deep}}\big) \;\le\; \rho(T)\cdot \mathfrak{R}_T(\mathcal{G}).\] Moreover, \[\mathfrak{R}_T(\mathcal{G}) \;\le\; \sqrt{k}\cdot\mathfrak{R}^{\mathrm{vec}}_T(\mathcal{V}_{L-1})\;+\;O\!\Big(\frac{1}{\sqrt{T}}\Big),\] where the \(\sqrt{k}\) is by Cauchy–Schwarz and the \(O(1/\sqrt{T})\) term comes from the free offset \(c\in[-1,1]\). Consequently, \[\mathfrak{R}_T\!\big(\mathcal{H}_{L,k,d}^{\mathrm{deep}}\big) \;\le\; \frac{C'_L\,k^{L/2}\rho(T)^{L}}{\sqrt{T}}.\]

Fat-shattering bound. By [5]: \[\alpha\sqrt{\min\{\mathop{\mathrm{fat}}_\alpha,T\}/T} \le C\,\mathfrak{R}_T(\mathcal{H}_{L,k,d}^{\mathrm{deep}}) \le C'_L\,k^{L/2}\rho(T)^{L}/\sqrt T.\] Choosing \(T=\Theta\!\big(\alpha^{-2}k^{L}\log^{3L}(ekL/\alpha)\big)\) forces \(\mathop{\mathrm{fat}}_\alpha<T\), hence \[\mathop{\mathrm{fat}}_{\alpha}\!\big(\mathcal{H}_{L,k,d}^{\mathrm{deep}}\big) \;\le\; C_L''\,\frac{k^{L}}{\alpha^2}\, \log^{3L}\!\Big(\frac{ekL}{\alpha}\Big).\] Plugging into the truncated multiscale sum: \[\sum_{\Delta_u>1/\sqrt d}\Delta_u^2 \;\le\; C_L\,k^{L} \sum_{r=-1}^{K}\log^{3L}\!\big(ekL/\alpha_r\big) \;=\; O\!\Big(k^{L}\log^{3L+1}(edkL)\Big).\]

8.0.0.2 Small gaps.

Apply Lemma 11 with \(\mathcal{H}=\mathcal{H}_{L,k,d}^{\mathrm{deep}}\) and \(\mathcal{F}=\mathcal{F}_{L,k,d}^{\mathrm{deep}}\): for the same branch \(P\), \[\sum_{\Delta_u\le 1/\sqrt d}\Delta_u^2 \;\le\; \frac{4}{d}\,\mathbb{D}_{\mathrm{onl}}(\mathcal{F}_{L,k,d}^{\mathrm{deep}};\ell_{\cap}).\] We bound \(\mathbb{D}_{\mathrm{onl}}(\mathcal{F}_{L,k,d}^{\mathrm{deep}};\ell_{\cap})\) via the entropy potential. Let \(K_2\) denote the \(\ell_2\) parameter Lipschitz constant: \(\|h_\theta-h_{\theta'}\|_\infty\le K_2\|\theta-\theta'\|_2\). Since \(\operatorname{ReLU}\) is \(1\)-Lipschitz and every weight matrix has spectral norm at most \(\sqrt{k}\) (each of \(k\) rows has \(\ell_2\)-norm \(\le 1\)), a standard inductive argument (analogous to Lemma 19 given in the next sections) gives \(K_2=O\big(k^{(L-1)/2}\sqrt{L}\big)\). Multiplying by \(\sqrt d\) for \(\mathcal{F}_{L,k,d}^{\mathrm{deep}}\), a volumetric cover of the parameter set \(\Theta\subseteq B_2(0,\sqrt{2Lk})\) in \(\mathbb{R}^p\) yields \[\log N(\mathcal{F}_{L,k,d}^{\mathrm{deep}},\varepsilon;\ell_\cap) \;\le\; p\,\log\!\Big(\frac{C\sqrt{Lkd}\,K_2}{\sqrt\varepsilon}\Big), \qquad \varepsilon\in(0,1].\] Integrating: \(\Phi(\mathcal{F}_{L,k,d}^{\mathrm{deep}})=O\!\big(p\,\log(C\sqrt{Lkd}\,K_2)\big)=O(pL\log(kd))\), and hence \(\mathbb{D}_{\mathrm{onl}}(\mathcal{F}_{L,k,d}^{\mathrm{deep}};\ell_{\cap})=O(pL\log(kd))\). Therefore \[\sum_{\Delta_u\le 1/\sqrt d}\Delta_u^2 \;=\; O\!\Big(\frac{pL\log(kd)}{d}\Big) \;=\; O\!\big(kL\log(kd)\big),\] since the \(kd/d=k\) term dominates for large \(d\).

Adding large- and small-gap contributions: \[\sum_{u\in P}\Delta_u^2 = O\!\Big(k^L\log^{3L+1}(edkL)+kL\log(kd)\Big) = O\!\Big(k^L\log^{3L+1}(edkL)\Big).\] Using \(\ell_{\cap}(s_{u,0},s_{u,1})=\Delta_u^2/4\) and the same reduction to squared loss as in 4 proves the claim. ◻

Proof. It is enough to prove the claim for even \(k\). If \(k\) is odd, use only \(k-1\) neurons in each hidden layer and set all other rows and output weights to zero; since \(L\) is fixed, this changes the lower bound only by a constant factor. Hence assume \(k\) is even.

First assume that \(d\) is a power of two. For each \(s=(s_1,\ldots,s_d)\in\{\pm1\}^d\), let \(v_s=s/\sqrt d\). In the first layer, set the first \(k/2\) rows of \(W_1\) equal to \(v_s\), set the last \(k/2\) rows equal to \(-v_s\), and set \(b_1=0\). For every \(\ell=2,\ldots,L-1\), set \(W_\ell=k^{-1/2}\mathbf{1}\mathbf{1}^\top\) and \(b_\ell=0\). Finally set \(a=\mathbf{1}\) and \(c=0\). All constraints are satisfied: \(\|v_s\|_2=\|-v_s\|_2=1\), every row of \(k^{-1/2}\mathbf{1}\mathbf{1}^\top\) has norm \(1\), all biases are zero, and all output weights are in \([-1,1]\).

For this network, the unclipped output is \((k^{L/2}/2)|\langle v_s,x\rangle|\). Indeed, after the first layer the sum of the \(k\) activations is \((k/2)|\langle v_s,x\rangle|\). Each fixed hidden layer maps a nonnegative vector with coordinate-sum \(R\) to the constant vector whose coordinates are all \(R/\sqrt k\), so the new coordinate-sum is \(\sqrt k R\). Applying this through the \(L-2\) fixed hidden layers gives final pre-clipped output \(k^{(L-2)/2}(k/2)|\langle v_s,x\rangle|=(k^{L/2}/2)|\langle v_s,x\rangle|\). Thus the class contains the functions \[h_s(x)=\textrm{clip}\left(\frac{k^{L/2}}{2}|\langle v_s,x\rangle|\right), \qquad s\in\{\pm1\}^d.\]

We construct a realizable scaled Littlestone tree for this subclass. The construction maintains a partition of \([d]=\{1,\ldots,d\}\) into dyadic intervals. For a block \(B\subseteq[d]\) and a sign vector \(s\in\{\pm1\}^d\), write \(s_B=(s_i)_{i\in B}\). Each current block \(B\) has a public reference pattern \(r_B\in\{\pm1\}^B\). The invariant is that the surviving signs are exactly those \(s\) such that, for every current block \(B\), either \(s_B=r_B\) or \(s_B=-r_B\). Initially the blocks are singletons and \(r_{\{i\}}(i)=1\), so all signs survive.

Consider a merge of two adjacent current blocks \(B_0,B_1\), each of size \(m/2\), and let \(B=B_0\cup B_1\). The tree node is labeled by \[x_B = \frac{1}{\sqrt m} \left( \sum_{i\in B_0}r_{B_0}(i)e_i + \sum_{i\in B_1}r_{B_1}(i)e_i \right).\] Then \(\|x_B\|_2^2=(|B_0|+|B_1|)/m=1\). If the two child blocks have the same orientation, meaning either \(s_{B_0}=r_{B_0}\) and \(s_{B_1}=r_{B_1}\), or \(s_{B_0}=-r_{B_0}\) and \(s_{B_1}=-r_{B_1}\), then \(|\langle v_s,x_B\rangle|=\sqrt{m/d}\). If they have opposite orientations, meaning either \(s_{B_0}=r_{B_0}\) and \(s_{B_1}=-r_{B_1}\), or \(s_{B_0}=-r_{B_0}\) and \(s_{B_1}=r_{B_1}\), then \(|\langle v_s,x_B\rangle|=0\). Thus the two outgoing labels \[0 \qquad\text{and}\qquad \alpha_m=\min\left\{\frac{k^{L/2}}{2}\sqrt{\frac{m}{d}},1\right\}\] are both realizable by surviving hypotheses.

After the high-label branch, keep exactly the surviving signs with the same orientation and define \(r_B\) by \(r_B(i)=r_{B_0}(i)\) for \(i\in B_0\) and \(r_B(i)=r_{B_1}(i)\) for \(i\in B_1\). After the zero-label branch, keep exactly the surviving signs with opposite orientations and define \(r_B\) by \(r_B(i)=r_{B_0}(i)\) for \(i\in B_0\) and \(r_B(i)=-r_{B_1}(i)\) for \(i\in B_1\). In both cases the surviving restrictions on \(B\) are exactly \(r_B\) and \(-r_B\), while all other blocks are unchanged. Hence the invariant is preserved, and the surviving set is nonempty on every branch.

The tree performs all merges bottom-up. At a level whose merged block size is \(m\), there are \(d/m\) nodes. For every level with \(m\le4d/k^L\), no clipping occurs, so \(\alpha_m^2=k^L m/(4d)\). Since \(\alpha_m\in[0,1]\) on these levels, \(\ell_{\cap}(0,\alpha_m)=\alpha_m^2/4=k^L m/(16d)\). Therefore the total gap contributed by such a level is \((d/m)\cdot k^Lm/(16d)=k^L/16\). The dyadic merged block sizes are \(m=2,4,\ldots,d\), and the condition \(m\le4d/k^L\) holds for \(\Omega(\log(d/k^L))\) levels whenever \(d/k^L\to\infty\). Hence every branch has total \(\ell_{\cap}\)-gap at least \(\Omega(k^L\log(d/k^L))\).

The tree is realizable by the invariant: along every branch, at least one sign vector survives, and the corresponding fixed hypothesis \(h_s\) realizes all labels on that branch. Therefore \[\mathbb{D}_{\mathrm{onl}}(\mathcal{H}_{L,k,d}^{\mathrm{deep}};\ell_{\cap})\ge\Omega(k^L\log(d/k^L))\] when \(d\) is a power of two.

For general \(d\), run the same construction on the first \(D=2^{\lfloor\log_2 d\rfloor}\) coordinates and set all remaining coordinates to zero in the queries and in the vectors \(v_s\). Since \(D\ge d/2\), the same lower bound follows whenever \(d/k^L\to\infty\). ◻

Proof. Let \(C_k := 1+4\bigl(k+\tfrac12\bigr)^2\). Suppose, towards a contradiction, that there is an \(\varepsilon\)-efficient proper algorithm \(\mathcal{A}\) for our (clipped) class \(\mathcal{H}_{k,d}\).

Given any realizable sample \(S=\{(x_i,y_i)\}_{i=1}^m\) with \(\|x_i\|_2\le 1\) and \(y_i\in[-\tfrac12,\tfrac12]\), run \(\mathcal{A}\) with accuracy parameter \(\varepsilon' := \varepsilon/C_k\) and obtain a hypothesis \(h=\mathrm{clip}(\tilde{h})\in\mathcal{H}_{k,d}\), where \(\tilde{h}(x)=\sum_{j=1}^k a_j\textrm{ReLU}(w^j\cdot x)\) is the unclipped network.

Let \(B:=\{i:\;|\tilde{h}(x_i)|>1\}\) be the indices where clipping is active. For every \(i\in B\) we have \(h(x_i)\in\{-1,1\}\) and \(|y_i|\le\tfrac12\), hence \((h(x_i)-y_i)^2\ge (1-\tfrac12)^2=\tfrac14\). Therefore, \[\frac{|B|}{m}\cdot \frac{1}{4} \;\le\;\frac{1}{m}\sum_{i\in B}(h(x_i)-y_i)^2 \;\le\;L_S(h)\;\le\;\varepsilon', \quad\text{so}\quad \frac{|B|}{m}\le 4\varepsilon'.\] On \([m]\setminus B\) we have \(h(x_i)=\tilde{h}(x_i)\), while on \(B\) we use \(|\tilde{h}(x_i)|\le k\) and \(|y_i|\le\tfrac12\) to bound \((\tilde{h}(x_i)-y_i)^2\le (k+\tfrac12)^2\). Thus, \[L_S(\tilde{h}) \;\le\;L_S(h) \;+\; \frac{|B|}{m}\bigl(k+\tfrac12\bigr)^2 \;\le\;\varepsilon' + 4\varepsilon'\bigl(k+\tfrac12\bigr)^2 \;=\;C_k\,\varepsilon' \;=\;\varepsilon.\]

Finally, convert \(\tilde{h}\) to the exact parameterization of [8] by setting \(\bar a_j:=\mathrm{sign}(a_j)\in\{\pm1\}\) (and if \(a_j=0\) take \(\bar a_j=1\)) and \(\bar w^j := |a_j|\,w^j\); then \(\|\bar w^j\|_2\le 1\) and \(\sum_{j=1}^k \bar a_j\textrm{ReLU}(\bar w^j\!\cdot x)=\sum_{j=1}^k a_j\textrm{ReLU}(w^j\!\cdot x)=\tilde{h}(x)\). Moreover, given any realizable instance of the bounded \(k\)-ReLU training problem with labels in \([-k,k]\), we can scale the labels by a factor \(\alpha\le 1/(2k)\) (and keep the same inputs) to obtain an equivalent realizable instance with labels in \([-\tfrac12,\tfrac12]\); an \(\varepsilon\)-approximate solution for the scaled instance yields a \((\varepsilon/\alpha^2)\)-approximate solution for the original instance. Choosing \(\alpha\) as a fixed constant (depending only on \(k\)) preserves \(\varepsilon\)-efficiency up to constant factors in \(1/\varepsilon\), and thus contradicts the results of [8]. ◻

Proof. Given a realizable sample \(S\), run \(\mathcal{A}\) for \(T:=m\) rounds on a randomized online sequence obtained by sampling indices \(i_t\sim\mathrm{Unif}([m])\) independently and feeding \((x_t,y_t)=(x_{i_t},y_{i_t})\) to \(\mathcal{A}\). Record the hypotheses \(h_1,\dots,h_T\in\mathcal{H}_{k,d}\) output by \(\mathcal{A}\).

Conditioned on the history up to round \(t\), we have \(\mathbb{E}[(h_t(x_{i_t})-y_{i_t})^2 \mid h_t]=L_S(h_t)\). Hence \[\mathbb{E}\!\left[\frac{1}{T}\sum_{t=1}^T L_S(h_t)\right] =\mathbb{E}\!\left[\frac{1}{T}\sum_{t=1}^T (h_t(x_{i_t})-y_{i_t})^2\right]\le \varepsilon.\] Therefore \(\mathbb{E}[\min_{t\le T} L_S(h_t)]\le \varepsilon\) (since \(\min\le\) average). By Markov, \(\Pr\big[\min_{t\le T} L_S(h_t) > 2\varepsilon\big]\le \tfrac12\). Compute \(L_S(h_t)\) for all \(t\) and output \(\hat{h}:=\arg\min_{t\le T} L_S(h_t)\); then \(\Pr[L_S(\hat{h})\le 2\varepsilon]\ge \tfrac12\). Run the procedure \(O(\log(1/\delta))\) times and output the best hypothesis found to boost success probability, and replace \(\varepsilon\) by \(\varepsilon/2\) to obtain \(L_S(\hat{h})\le \varepsilon\) with high constant probability. The runtime remains \(2^{o(1/\varepsilon)}\mathrm{poly}(d,m)\). ◻

Proof. Otherwise Lemma 16 would yield an \(\varepsilon\)-efficient proper batch algorithm, contradicting Theorem 19. ◻

Proof. Fix \(\varepsilon\in(0,1]\). For every \(\theta\in[-1+\varepsilon,1]\), define \[f_{\varepsilon,\theta}(x)\;:=\;\operatorname{ReLU}(\theta-x)\;-\;\operatorname{ReLU}(\theta-x-\varepsilon),\qquad x\in[-1,1].\] We first verify that \(f_{\varepsilon,\theta}\in\mathcal{N}\). Consider a two-hidden-unit ReLU network \[x\;\mapsto\;a_1\,\operatorname{ReLU}(w_1 x+b_1)\;+\;a_2\,\operatorname{ReLU}(w_2 x+b_2)\;+\;b .\] Set \[w_1=w_2=-1,\qquad b_1=\theta,\qquad b_2=\theta-\varepsilon,\qquad a_1=1,\qquad a_2=-1,\qquad b=0.\] All parameters have absolute value at most \(1\) since \(\theta\in[-1+\varepsilon,1]\) and \(\varepsilon\le 1\), and this choice implements \(f_{\varepsilon,\theta}\).

Next, note that for any \(x\in[-1,1]\): \[\label{eq:f-threshold-behavior} f_{\varepsilon,\theta}(x)= \begin{cases} 0, & x\ge \theta,\\ \varepsilon, & x\le \theta-\varepsilon, \end{cases}\tag{10}\] (and for \(x\in(\theta-\varepsilon,\theta)\) the value lies in \((0,\varepsilon)\)). Indeed, if \(x=\theta+\delta\) with \(\delta\ge0\), then \[f_{\varepsilon,\theta}(x)=\operatorname{ReLU}(-\delta)-\operatorname{ReLU}(-\delta-\varepsilon)=0-0=0.\] If \(x=\theta-\varepsilon'\) with \(\varepsilon'\ge \varepsilon\), then \[f_{\varepsilon,\theta}(x)=\operatorname{ReLU}(\varepsilon')-\operatorname{ReLU}(\varepsilon'-\varepsilon)=\varepsilon'-(\varepsilon'-\varepsilon)=\varepsilon.\]

We now show that for every \(d\in\mathbb{N}\) there exists a complete binary tree of depth \(d\) that is shattered by \[\mathcal{F}_\varepsilon\;:=\;\{f_{\varepsilon,\theta}:\;\theta\in[-1+\varepsilon,1]\}\subseteq \mathcal{N},\] and hence \(\mathrm{Ldim}(\mathcal{N})=\infty\).

Fix \(d\in\mathbb{N}\) and set \(\varepsilon:=2^{-d-2}\). We construct a depth-\(d\) shattered tree as follows. Label every left edge by \(0\) and every right edge by \(\varepsilon\). For each node \(v\) we maintain an interval \(I_v=[L_v,U_v]\subseteq[-1+\varepsilon,1]\) of thresholds consistent with the labels along the path from the root to \(v\).

At the root, set \(I_{\mathrm{root}}=[-1+\varepsilon,1]\). Given an internal node \(v\) with \(I_v=[L_v,U_v]\) satisfying \(|I_v|:=U_v-L_v>\varepsilon\), label \(v\) by \[x_v\;:=\;\frac{L_v+U_v-\varepsilon}{2}.\] Then \(x_v\in[L_v,U_v]\) and \(x_v+\varepsilon\in[L_v,U_v]\). Let \(v_\ell\) and \(v_r\) denote the left and right children of \(v\). Define \[\label{eq:update} I_{v_\ell}:=[L_v,x_v],\qquad I_{v_r}:=[x_v+\varepsilon,U_v].\tag{11}\] These intervals are nonempty since \(|I_v|>\varepsilon\). Moreover, by 10 , for every \(\theta\in I_{v_\ell}\) we have \(f_{\varepsilon,\theta}(x_v)=0\), and for every \(\theta\in I_{v_r}\) we have \(f_{\varepsilon,\theta}(x_v)=\varepsilon\). Thus the labeling choice at \(v\) is realizable by \(\mathcal{F}_\varepsilon\) and the recursive update maintains the consistency invariant.

It remains to verify that along every path, the recursion can proceed for at least \(d\) levels, i.e., that \(|I_v|>\varepsilon\) for all nodes \(v\) of depth at most \(d\). Let \(\ell_t\) denote the length \(|I_v|\) at depth \(t\) (it is the same for all nodes at the same depth by symmetry of the construction). From 11 , \[\ell_0 = 2-\varepsilon,\qquad \ell_t = \frac{\ell_{t-1}-\varepsilon}{2}\quad\text{for }t\ge 1.\] Solving yields \(\ell_t = 2^{-t+1}-\varepsilon\), which can be checked by induction: \[\ell_t=\frac{(2^{-t+2}-\varepsilon)-\varepsilon}{2}=2^{-t+1}-\varepsilon.\] In particular, \[\ell_d = 2^{-d+1}-\varepsilon= 2^{-d+1}-2^{-d-2} = 2^{-d-2}(8-1) > 2^{-d-2}=\varepsilon.\] Therefore all nodes up to depth \(d\) satisfy \(|I_v|>\varepsilon\), so the constructed tree is a complete depth-\(d\) shattered tree for \(\mathcal{F}_\varepsilon\subseteq\mathcal{N}\). Since \(d\) was arbitrary, \(\mathrm{Ldim}(\mathcal{N})=\infty\). ◻

Proof of 1. Fix any scaled Littlestone tree \(\mathcal{T}\) for \(\mathcal{H}\). By Theorem 10, there exists a branch \(y\in\mathcal{P}(\mathcal{T})\) such that \(\sum_i \gamma_{y_i}\le 4c\,\Phi(\mathcal{H})\). Therefore, \[\inf_{y\in\mathcal{P}(\mathcal{T})}\sum_i \gamma_{y_i}\;\le\;4c\,\Phi(\mathcal{H}).\] Taking the supremum over \(\mathcal{T}\) in the definition of \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\) gives the claim. ◻

Proof. By the assumed covering bound, \[\log_2 N(\mathcal{H},\varepsilon)\;\le\;p\log_2(A/\varepsilon)\;=\;p\log_2 A + p\log_2(1/\varepsilon).\] Integrating over \(\varepsilon\in(0,1]\) gives \[\Phi(\mathcal{H}) \le p\log_2 A + p\int_0^1 \log_2(1/\varepsilon)\,d\varepsilon = p\log_2 A + \frac{p}{\ln 2},\] using \(\int_0^1 \ln(1/\varepsilon)\,d\varepsilon= 1\). The bound on \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\) follows from 1. ◻

Proof. Fix \(\varepsilon>0\) and set \(r:=\omega^{\leftarrow}(\varepsilon)\). Let \(S\subseteq\Theta\) be an \(r\)-cover of \(\Theta\) under \(\|\cdot\|\). Define \(\mathcal{N}:=\{h_s:\;s\in S\}\subseteq \mathcal{H}\). For any \(\theta\in\Theta\) choose \(s\in S\) such that \(\|\theta-s\|\le r\). By \(\omega\)-Lipschitzness and monotonicity of \(\omega\), \[d_\ell(h_\theta,h_s)\;\le\;\omega(\|\theta-s\|)\;\le\;\omega(r)\;\le\;\varepsilon,\] where \(\omega(r)\le \varepsilon\) holds by the definition of \(r=\omega^{\leftarrow}(\varepsilon)\) and the fact that \(\omega\) is continuous. Thus \(\mathcal{N}\) is an \(\varepsilon\)-cover of \(\mathcal{H}\). Minimizing over such \(S\) yields \(N(\mathcal{H},\varepsilon)\le N(\Theta,r)=N(\Theta,\omega^{\leftarrow}(\varepsilon))\). ◻

Proof. By Lemma 17, for every \(\varepsilon>0\), \(\log_2 N(\mathcal{H},\varepsilon)\le \log_2 N(\Theta,\omega^{\leftarrow}(\varepsilon))\). Integrating over \((0,\operatorname{diam}(\mathcal{H})]\) gives the claim (the integrands are measurable as \(\varepsilon\mapsto N(\cdot,\varepsilon)\) is nonincreasing). ◻

Proof. For \(\varepsilon\in(0,1]\), Lemma 17 with \(\omega(t)=Lt\) gives \(N(\mathcal{H},\varepsilon)\le N(\Theta,\varepsilon/L)\) (since \(\omega^{\leftarrow}(\varepsilon)=\varepsilon/L\)). If \(L\ge 1\) then \(N(\Theta,\varepsilon/L)\le (CL/\varepsilon)^p\). If \(L<1\) then \(\varepsilon/L>1\), so by monotonicity \(N(\Theta,\varepsilon/L)\le N(\Theta,1)\le C^p\le (C/\varepsilon)^p\).

In both cases, \[N(\mathcal{H},\varepsilon)\;\le\;\Big(\frac{C\max\{L,1\}}{\varepsilon}\Big)^p.\] Therefore, \[\log_2 N(\mathcal{H},\varepsilon)\;\le\;p\log_2\!\big(C\max\{L,1\}\big)+p\log_2(1/\varepsilon).\] Integrating over \(\varepsilon\in(0,1]\) yields \[\Phi(\mathcal{H})\;\le\;p\log_2\!\big(C\max\{L,1\}\big)+p\int_0^1 \log_2(1/\varepsilon)\,d\varepsilon \;=\;p\log_2\!\big(C\max\{L,1\}\big)+\frac{p}{\ln 2},\] using \(\int_0^1 \ln(1/\varepsilon)\,d\varepsilon=1\). ◻

Proof. For \(\varepsilon\in(0,1]\), Lemma 17 with \(\omega(t)=(Lt)^q\) gives \[N(\mathcal{H},\varepsilon)\;\le\;N\!\Big(\Theta,\,\omega^{\leftarrow}(\varepsilon)\Big) \;=\;N\!\left(\Theta,\,\frac{\varepsilon^{1/q}}{L}\right),\] since \(\omega^{\leftarrow}(\varepsilon)=\varepsilon^{1/q}/L\). If \(L\ge 1\) then \(N(\Theta,\varepsilon^{1/q}/L)\le (CL/\varepsilon^{1/q})^p\). If \(L<1\) then \(\varepsilon^{1/q}/L>1\), so by monotonicity \(N(\Theta,\varepsilon^{1/q}/L)\le N(\Theta,1)\le C^p\le (C/\varepsilon^{1/q})^p\). In both cases, \[N(\mathcal{H},\varepsilon)\;\le\;\Big(\frac{C\max\{L,1\}}{\varepsilon^{1/q}}\Big)^p.\] Thus \(\log_2 N(\mathcal{H},\varepsilon)\le p\log_2\!\big(C\max\{L,1\}\big)+\frac{p}{q}\log_2(1/\varepsilon)\). Integrating over \(\varepsilon\in(0,1]\) yields the displayed bound, using again \(\int_0^1 \log_2(1/\varepsilon)\,d\varepsilon= 1/\ln 2\). ◻

Proof. Since \(\Theta=\{u:\|u\|_\infty\le 1\}\), we have \(R_\Theta=\sup_{\|u\|_\infty\le 1}\|u\|=\alpha\). Let \(\delta:=\min\{1,r/\alpha\}\). If \(\|u-v\|_\infty\le \delta\), then \(u-v=\delta z\) for some \(z\) with \(\|z\|_\infty\le 1\), hence \(\|u-v\|=\delta\|z\|\le \delta\alpha\le r\). Therefore, any \(\delta\)-cover of \(\Theta\) in \(\|\cdot\|_\infty\) is an \(r\)-cover in \(\|\cdot\|\). A uniform grid in \([-1,1]^p\) with mesh \(\delta\) has size at most \((2/\delta+1)^p\), so \[N(\Theta,r)\;\le\;\left(\frac{2}{\delta}+1\right)^p \le \left(1+\frac{2\alpha}{r}\right)^p.\] If moreover \(r\le 2\alpha\), then \(2\alpha/r\ge 1\) and thus \(1+2\alpha/r\le 4\alpha/r\), giving \(N(\Theta,r)\le (4\alpha/r)^p\). ◻

Proof. If \(K=0\) then 13 implies \(h_\theta\) is constant over \(\theta\in\Theta\), hence \(N(\mathcal{H},\varepsilon)=1\) for all \(\varepsilon>0\) and the claims are immediate. Assume henceforth \(K>0\). For any \(\theta,\theta'\in\Theta\), \[d_\ell(h_\theta,h_{\theta'}) =\sup_{x\in\mathcal{X}}\ell\big(h_\theta(x),h_{\theta'}(x)\big) \le \sup_{x\in\mathcal{X}}\varphi\big(|h_\theta(x)-h_{\theta'}(x)|\big) \le \varphi\big(\|h_\theta-h_{\theta'}\|_\infty\big) \le \varphi\big(K\|\theta-\theta'\|\big).\] Thus, any \(r\)-cover of \(\Theta\) in \(\|\cdot\|\) induces a \(\varphi(Kr)\)-cover of \(\mathcal{H}\) in \(d_\ell\), and therefore \[N(\mathcal{H},\varepsilon)\;\le\;N\!\left(\Theta,\;\frac{\varphi^{\leftarrow}(\varepsilon)}{K}\right).\] Set \(r:=\varphi^{\leftarrow}(\varepsilon)/K\). Since \(\Theta\) has diameter at most \(2R_\Theta=2\alpha\) under \(\|\cdot\|\), 13 implies \(\|h_\theta-h_{\theta'}\|_\infty\le 2\alpha K\) for all \(\theta,\theta'\in\Theta\), hence \(\operatorname{diam}(\mathcal{H})\le \varphi(2\alpha K)\) and so \(\varphi^{\leftarrow}(\varepsilon)\le 2\alpha K\) for all \(\varepsilon\le\operatorname{diam}(\mathcal{H})\). Therefore \(r\le 2\alpha\), and Lemma 18 yields \[N(\mathcal{H},\varepsilon)\;\le\;\left(\frac{4\alpha}{r}\right)^p =\left(\frac{4\alpha K}{\varphi^{\leftarrow}(\varepsilon)}\right)^p.\] Taking \(\log_2\) and integrating over \(\varepsilon\in(0,\operatorname{diam}(\mathcal{H})]\) gives the bound on \(\Phi(\mathcal{H})\). If \(\varphi(t)=t^q\) and \(\operatorname{diam}(\mathcal{H})\le 1\), then \(\varphi^{\leftarrow}(\varepsilon)=\varepsilon^{1/q}\) and \[\int_0^1 \log_2\!\Big(\frac{1}{\varepsilon^{1/q}}\Big)\,d\varepsilon =\frac{1}{q}\int_0^1 \log_2(1/\varepsilon)\,d\varepsilon =\frac{1}{q\ln 2},\] which yields the final bound. ◻

Proof. Since \(\mathrm{clip}_{[0,1]}\) is \(1\)-Lipschitz, it suffices to bound the corresponding unclipped outputs. Fix \(x\in\mathcal{X}\) and write \(z^{(\ell)}(x)\) and \({z'}^{(\ell)}(x)\) for the hidden vectors under \(\theta\) and \(\theta'\). By induction, using \(|\sigma(t)|\le |\sigma(0)|+L_\sigma|t|\), \(\|W_1 v\|_\infty\le d\|v\|_\infty\) for \(W_1\in[-1,1]^{k\times d}\), \(\|Wv\|_\infty\le k\|v\|_\infty\) for \(W\in[-1,1]^{k\times k}\), and \(\|b_\ell\|_\infty\le 1\), we get \(\|z^{(\ell)}(x)\|_\infty\le M_\ell\) and \(\|{z'}^{(\ell)}(x)\|_\infty\le M_\ell\) for all \(\ell\).

Let \(\Delta_\ell:=\|z^{(\ell)}(x)-{z'}^{(\ell)}(x)\|_1\). Using Lipschitzness of \(\sigma\) and \(\|Wv\|_1\le k\|v\|_1\) (since each column sum of \(|W|\) is at most \(k\)), one obtains \[\Delta_\ell \;\le\; L_\sigma\Big(k\Delta_{\ell-1} +\bar M\|W_\ell-W'_\ell\|_1 +\|b_\ell-b'_\ell\|_1\Big), \qquad \ell=1,\dots,L-1.\] Unrolling this recursion gives \[\Delta_{L-1} \;\le\; L_\sigma(\bar M+1)\Big(\sum_{s=0}^{L-2}(L_\sigma k)^s\Big)\,\|\theta-\theta'\|_1 \;=\; L_\sigma(\bar M+1)S\,\|\theta-\theta'\|_1.\] Finally, \[|\langle a,z^{(L-1)}(x)\rangle+c-\langle a',{z'}^{(L-1)}(x)\rangle-c'| \;\le\; \Delta_{L-1}+\bar M\|a-a'\|_1+|c-c'| \;\le\; K_{L,k,\sigma}\|\theta-\theta'\|_1,\] and taking \(\sup_{x\in\mathcal{X}}\) yields the claim. ◻

Proof. Let \(\mathcal{X}=\{x_1,x_2,\dots\}\) and let \(a_k=2^{-k}\) and \(m_k:=2^{2^k}\), so \(a_k\log_2 m_k=1\) for all \(k\). It follows that \((a_k)_{k\ge1}\subset(0,1]\) is a strictly decreasing sequence with \(a_k\downarrow 0\) and \(\sum_{k\ge1} a_k<\infty\). Let \[\mathcal{Y}\;:=\;\{(k,i): k\ge1,\;i\in[m_k]\}.\] Define \(\ell:\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}_{\ge0}\) by \[\ell\big((k,i),(k',i')\big):= \begin{cases} 0, & (k,i)=(k',i'),\\ a_k, & k=k',\;i\neq i',\\ \max\{a_k,a_{k'}\}, & k\neq k'. \end{cases}\] Then \(\ell\) is a metric: for any \(y_1,y_2,y_3\in\mathcal{Y}\), \(\ell(y_1,y_2)\le \max\{\ell(y_1,y_3),\ell(y_2,y_3)\}\), which is immediate from the case analysis (\(\max\{\cdot,\cdot\}\) always dominates the larger scale among the involved blocks). Define the hypothesis class \[\mathcal{H}\;:=\;\big\{h:\mathcal{X}\to\mathcal{Y}:\;\exists (i_k)_{k\ge1}\text{ with }h(x_k)=(k,i_k)\;\forall k\big\}.\] For the induced metric \(d_\ell(f,g)=\sup_{x\in\mathcal{X}}\ell(f(x),g(x))\), we have \[d_\ell(f,g)=\max\{a_k:\;f(x_k)\neq g(x_k)\},\] so \(\operatorname{diam}(\mathcal{H})=a_1<\infty\).

13.0.0.1 Finite \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\).

Fix any scaled Littlestone tree for \(\mathcal{H}\). If a node queries \(x_k\) for the first time along a branch, then both outgoing edge labels must lie in \(\{(k,i):i\in[m_k]\}\), so its gap is either \(0\) (same label) or \(a_k\) (distinct labels). After the branch takes one of these edges, the value of \(h(x_k)\) is fixed in the version space along that branch; hence any later query of \(x_k\) on the same branch can only have both children nonempty if both edge labels coincide with that fixed value, yielding gap \(0\). Therefore, along every branch the total gap is at most \(\sum_{k\ge1} a_k\), and hence for every tree \(\inf_{y}\sum_i \gamma_{y_i}\le \sum_{k\ge1} a_k.\) Taking the supremum over trees gives \[\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\;\le\;\sum_{k\ge1} a_k\;<\;\infty.\]

13.0.0.2 Infinite \(\Phi(\mathcal{H})\).

For \(\varepsilon>0\), let \(K(\varepsilon):=\max\{k: a_k>\varepsilon\}\) (which is finite as \(a_{k} \downarrow 0\)) where \(K(\varepsilon) = 0\) for \(\varepsilon\geq a_1\). Then two hypotheses are within \(d_\ell\)-distance \(\le\varepsilon\) iff they agree on all coordinates \(x_1,\dots,x_{K(\varepsilon)}\). Thus, for every \(f\in\mathcal{H}\) we have \[B_{d_\ell}(f,\varepsilon) =\{g\in\mathcal{H}:\;g(x_i)=f(x_i)\;\forall i\le K(\varepsilon)\},\] where \(B_{d_\ell}(f,\varepsilon):=\{g\in\mathcal{H}:\;d_\ell(f,g)\le \varepsilon\}\) denotes the (closed) \(\varepsilon\)-ball around \(f\) in \((\mathcal{H},d_\ell)\). In particular, any \(\varepsilon\)-cover must contain at least one element from each choice of \((h(x_1),\dots,h(x_{K(\varepsilon)}))\), so \(N(\mathcal{H},\varepsilon)\ge \prod_{i=1}^{K(\varepsilon)} m_i\). Conversely, fixing one representative for each such choice yields an \(\varepsilon\)-cover, hence \[N(\mathcal{H},\varepsilon)\;=\;\prod_{i=1}^{K(\varepsilon)} m_i \qquad(\varepsilon>0).\]

Since \(K(\varepsilon)=k\) for all \(\varepsilon\in(a_{k+1},a_k)\), we get \[\begin{align} \Phi(\mathcal{H}) &=\int_0^{a_1}\log_2 N(\mathcal{H},\varepsilon)\,d\varepsilon =\sum_{k\ge1}(a_k-a_{k+1})\sum_{i=1}^k \log_2 m_i\\ &=\lim_{n\to\infty}\Big(\sum_{k=1}^n a_k\log_2 m_k \;-\; a_{n+1}\sum_{i=1}^n \log_2 m_i\Big). \end{align}\] For \(a_k=2^{-k}\) and \(m_k=2^{2^k}\) we have \(\sum_{k=1}^n a_k\log_2 m_k=n\) and \(a_{n+1}\sum_{i=1}^n \log_2 m_i = 1-2^{-n}\to 1\), hence \(\Phi(\mathcal{H})=+\infty\). Moreover, \(\mathbb{D}_{\mathrm{onl}}(\mathcal{H})\le \sum_{k\ge1} a_k = \sum_{k\ge1}2^{-k}=1\). ◻