One-sided coordinate Rademacher contraction

Let $m\ge 1$, let $z_1,\dots ,z_m$ be fixed points in a set $\mathcal{Z}$, and let $\mathcal{H}$ be a nonempty class of functions $h:\mathcal{Z}\to \mathbb{R}$. For each $i$, let ${\mathrm{\Phi }}_i:\mathbb{R}\to \mathbb{R}$ be $L$-Lipschitz for one common $L\ge 0$. Suppose either that $\mathcal{H}$ is finite or countable, or that it has a specified nonempty countable subclass ${\mathcal{H}}_0$ for which, for every sign vector $\sigma \in \{-1,+1{\}}^m$, both displayed suprema equal the corresponding suprema over ${\mathcal{H}}_0$. Assume the suprema are finite. With independent uniform signs ${\sigma }_1,\dots ,{\sigma }_m$ and the one-sided normalization

${\widehat{\mathfrak{R}}}_S(\mathcal{H}):=\frac{1}{m}{\mathbb{E}}_{\sigma }{\sup }_{h\in \mathcal{H}}{\sum }_{i=1}^m{\sigma }_{i}h(z_i),$

one has

$\frac{1}{m}{\mathbb{E}}_{\sigma }{\sup }_{h\in \mathcal{H}}{\sum }_{i=1}^m{\sigma }_i{\mathrm{\Phi }}_i(h(z_i))\le L{\widehat{\mathfrak{R}}}_S(\mathcal{H})\mathrm{.}$

No condition ${\mathrm{\Phi }}_i(0)=0$ is required.

One-sided empirical Rademacher complexity: fixes the nonabsolute sign supremum and $1\mathrm{/}m$ normalization.

One-sided coordinate Rademacher contraction: proves this inequality for finite or countable classes, including the no-zero-at-zero case.

Mohri et al., Lemma 5.7, printed pp. 93–94: states the coordinatewise one-sided factor-$L$ contraction under the same normalization.

Bartlett and Mendelson, Theorem 12(4), printed p. 469: uses a different absolute-value convention, assumes the scalar map vanishes at zero, and has factor $2L$; that convention is not used here.