Uniform margin-risk deviation from empirical Rademacher complexity

Let $\mathrm{\Theta }$ be the set of all feasible tuples $(A_1,\dots ,A_L)$. The mixed-norm constraints are closed because each is a finite sum of continuous Euclidean column norms. For each layer, $\parallel A_i{\parallel }_{\sigma }\le s_i$ is the intersection, over all unit vectors $v$, of the closed conditions $\parallel A_{i}v{\parallel }_2\le s_i$, by the induced-operator-norm definition. Each column $A_i{e}_j$ then has norm at most $s_i$, so all matrix entries are bounded. Hence $\mathrm{\Theta }$ is closed and bounded in finite-dimensional Euclidean space and is compact by [F2].

For fixed $x$, induction over the layers shows that the score vector depends continuously on the matrix tuple: matrix multiplication is jointly continuous and each Lipschitz activation is continuous. Finite maxima, coordinate differences, and the ramp preserve continuity, so for fixed $(x,y)$ the loss $A\mapsto {\mathrm{\ell }}_{\gamma }(-m_{F_A}(x,y))$ is continuous. If $A^{(r)}\to A$, these losses converge pointwise in $(x,y)$ and are bounded by one, so [F3] shows that $A\mapsto R_{\gamma }(F_A)$ is continuous. Each empirical loss and each finite signed sum of losses is also continuous in $A$.

Identify the parameter tuples with ${\mathbb{R}}^p$, where $p:={\sum }_{i=1}^L{d}_i{d}_{i-1}$. The balls $B(q,r)$ with $q\in {\mathbb{Q}}^p$ and $r\in {\mathbb{Q}}_{>0}$ form a countable family: each rational is a quotient of an integer by a positive integer, the integers have the enumeration $0,1,-1,2,-2,\dots$, and finite tuples of natural numbers are enumerated by iterating the diagonal pairing $\pi (a,b):=(a+b)(a+b+1)\mathrm{/}2+b$. They form a base because for any open $O\subseteq {\mathbb{R}}^p$ and $x\in O$, choose $\eta >0$ with $B(x,\eta )\subseteq O$, then use [F9] in each coordinate interval $(x_j-\eta \mathrm{/}(4\sqrt{p}),x_j+\eta \mathrm{/}(4\sqrt{p}))$ to choose $q\in {\mathbb{Q}}^p$ with $\parallel q-x{\parallel }_2<\eta \mathrm{/}4$. Use [F9] again to choose a rational $r$ with $\parallel q-x{\parallel }_2<r<\eta -\parallel q-x{\parallel }_2$ (a nonempty interval with positive upper endpoint); then $x\in B(q,r)\subseteq B(x,\eta )\subseteq O$. Intersecting these balls with $\mathrm{\Theta }$ gives a countable base for its subspace topology. Using [F5], choose one point of $\mathrm{\Theta }$ from each nonempty basic intersection; the selected countable subset is dense in $\mathrm{\Theta }$. By step 2.1, each supremum over $\mathrm{\Theta }$ defining the uniform deviation or a signed empirical supremum equals the supremum over this countable dense subset. The losses are Borel in $(x,y)$ because the scores are continuous in $x$, the margin is a finite minimum of continuous score-coordinate differences, and the label set is finite. These countable suprema are therefore measurable.

Write $Z(S):={\sup }_{F\in \mathcal{F}}(R_{\gamma }(F)-{\widehat{R}}_{\gamma ,S}(F))$. Let $S^{\mathrm{\prime }}$ be an independent ghost sample from $D$. By the integral identities in [F4] and the inequality ${\sup }_F{\mathbb{E}}_{S^{\mathrm{\prime }}}{U}_F\le {\mathbb{E}}_{S^{\mathrm{\prime }}}{\sup }_F{U}_F$, $\mathbb{E}Z(S)\le {\mathbb{E}}_{S,S^{\mathrm{\prime }}}{\sup }_{F\in \mathcal{F}}\frac{1}{n}{\sum }_{i=1}^n({\mathrm{\ell }}_F(x_i^{\mathrm{\prime }},y_i^{\mathrm{\prime }})-{\mathrm{\ell }}_F(x_i,y_i)),$ where ${\mathrm{\ell }}_F(x,y)={\mathrm{\ell }}_{\gamma }(-m_F(x,y))$. Swapping each iid pair $(z_i,z_i^{\mathrm{\prime }})$ leaves its law unchanged; introducing independent uniform signs ${\epsilon }_i$ therefore leaves this expectation unchanged when each difference is multiplied by ${\epsilon }_i$. The supremum of a sum is at most the sum of the suprema, and symmetry of the signs gives $\mathbb{E}Z(S)\le 2{\mathbb{E}}_S{\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })$.

Replacing one sample coordinate changes $Z(S)$ by at most $1\mathrm{/}n$, since every loss lies in $[0,1]$; it also changes ${\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })$ by at most $1\mathrm{/}n$, by [F7] and the same range bound. Apply the upper-tail bound [F6] to $Z$ and to $-{\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })$, each with failure probability $\delta \mathrm{/}2$ and $t=\sqrt{\log (2\mathrm{/}\delta )\mathrm{/}(2n)}$. Outside a set of probability at most $\delta$, both $Z(S)\le \mathbb{E}Z(S)+t$ and $\mathbb{E}{\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })\le {\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })+t$. Combining with step 4.1 gives $Z(S)\le \mathbb{E}Z(S)+t\le 2\mathbb{E}{\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })+t\le 2{\widehat{\mathfrak{R}}}_S({\mathcal{L}}_{\gamma })+3t$.

If the predicted label differs from $y$, some competing score is at least the true-label score, so $m_F(x,y)\le 0$ and ${\mathrm{\ell }}_{\gamma }(-m_F(x,y))=1$. Hence the zero-one loss is pointwise at most the ramp loss. Also ${\mathrm{\ell }}_{\gamma }(-m)\le \mathbf{1}\{m\le \gamma \}$ for every real $m$, so empirical ramp risk is at most empirical margin loss. Apply the definition of $Z(S)$ and step 5.1 to conclude the stated bound for every $F\in \mathcal{F}$ simultaneously.