Is the following true?

Let $(x_1,...,x_N)$ be a set of points on the unit sphere $S^{d-1}$. Let $\ell_x: [-1,1]\rightarrow [0,1]$ be a family of Lipschitz functions indexed by $x\in S^{d-1}$, with corresponding Lipschitz constants $L_x$. Let $\sigma$ be a vector of Rademacher variables ($\pm 1$ with equal probability). Then, for any set $H$ of real valued functions, \begin{eqnarray} \frac{1}{N} E_{\sigma}[\sup_{h\in H}\sum_{n=1}^N \sigma_n (\ell_{x_n}\circ h) (x_n)] \le \frac{1}{N} E_{\sigma}[\sup_{h\in H}\sum_{n=1}^N L_{x_n} \sigma_n h(x_n)] \end{eqnarray}

If $\ell_x(\cdot)$ would be the same for all $x$ then the LHS would be the empirical Rademacher complexity of $\ell\circ H$, and the above inequality would hold by the Talagrand contraction lemma. Does this modified form exist? Is it likely to be true?

Update: No longer interesting (for the reason in the answer).


This seems to be easy by modifying the proof of the original, but not very useful, as in practice we need to take the sup w.r.t. $h, \forall \ell_{x_n}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.