2
$\begingroup$

Let $\{\varepsilon_i\}_{i=1}^n$ be a sequence of independent Radecmacher (i.e., symmetric Bernoulli) variables, and let $\phi_i :\mathbb R \to \mathbb R$ be contraction (i.e., 1-Lipschitz) mappings that vanish at zero ($\phi_i(0) = 0$). Finally, let $F :[0,\infty) \to \mathbb R$ be a nonnegative, nondecreasing convex function. Then, \begin{align*} \mathbb E F \Big( \frac12 \sup_{t \in T} \Big|\sum_{i=1}^n \varepsilon_i \phi_i(t_i) \Big|\Big) \le \mathbb E F \Big( \Big|\sup_{t \in T} \sum_{i=1}^n \varepsilon_i t_i \Big|\Big) \end{align*} where $t = (t_1,\dots,t_n)$ and $T$ is a bounded subset of $\mathbb R^n$. This result is known as the Ledoux--Talagrand contraction principle. First (minor) question:

Is the "vanishing at zero assumption" necessary? I have seen results without this assumption for the case where $F$ is the identity map. Can we drop it for general $F$?

The main question is about the extension of this result to the multivariate case where each $\phi_i$ is mapping $\mathbb R^d$ to $\mathbb R$, $t_i \in T_i \subset \mathbb R^d$ and $T = \prod_i T_i$. We let $t_{ik}, k= 1,\dots,d$ denote the coordinates of $t_i$. I can find two extensions to this setting in the literature:

  1. A result of A. Maurer that gives \begin{align*} \mathbb E \sup_{t \in T} \sum_{i=1}^n \varepsilon_i \phi_i(t_i) \le \sqrt 2 \mathbb E \sup_{t \in T} \sum_{i=1}^n \sum_{k=1}^d \varepsilon_{ik} t_{ik} \end{align*} where $\{\varepsilon_{ik}\}_{i,k}$ is an independent Radecmacher sequence and $\phi_i: \mathbb R^d \to \mathbb R$ are assumed to be contractions w.r.t. the $\ell_2$ norm on the input space.

  2. A result of S. van der Geer that gives \begin{align*} \mathbb E \sup_{t \in T} \Big|\sum_{i=1}^n \varepsilon_i \big(\phi_i(t_i) - \phi_i(t^*)\big)\Big| \le C 2^{d-1} \mathbb E \sup_{t \in T} \Big|\sum_{i=1}^n \sum_{k=1}^d g_{ik} (t_{ik} - t^*_k) \Big| \end{align*} where $\{g_{i,k}\}_{i,k}$ is a sequence of i.i.d. $N(0,1)$ variables, $t^* \in T$ and $\phi_i: \mathbb R^d \to \mathbb R$ are assumed to be contractions w.r.t. the $\ell_1$ norm on the input space.

Both of these results are extension of the "$F = $ identity case" of the original result. My question:

Are there similar extensions (hopefully with constants not exponentially dependent on $d$) for the case of the general $F$ in the original result. In particular, $F(x) = e^{\lambda x}$ for $\lambda > 0$ is of interest for bounding moment-generating functions.

$\endgroup$
2
  • 1
    $\begingroup$ Vanishing at zero is necessary. Consider $T=\{0\}$, $\phi_j(t)=2N$. The inequality becomes $E F(N|\sum \varepsilon_j|)\leq F(0)$ this cannot hold for all constants $N$ unless $F$ is constant. $\endgroup$ Commented May 10, 2021 at 3:30
  • $\begingroup$ @PaataIvanishvili, OK, thanks. I guess if there is no absolute value around the "sup" on both sides and F is the identity map, then vanishing at zero can be removed (?) $\endgroup$
    – passerby51
    Commented May 10, 2021 at 5:53

0

You must log in to answer this question.

Browse other questions tagged .