4
$\begingroup$

Let $\mathcal{C}\in\mathbb{R}^n$ be a subset of the unit ball. Also let $\mathbf{a}_1,\mathbf{a}_2,\ldots,\mathbf{a}_m\in\mathbb{R}^n$ be i.i.d. random Gaussian vectors $\mathcal{N}(\mathbf{0},\mathbf{I})$ then by Gordon's lemma we know \begin{align*} \underset{\mathbf{y}\in\mathcal{C}}{\sup}\bigg|\frac{1}{m}\sum_{k=1}^m (\mathbf{a}_k^T\mathbf{y})^2-\|\mathbf{y}\|_{\ell_2}^2\bigg|\le \delta, \end{align*} holds with high probability as long as \begin{align*} m\ge c\frac{\omega^2(\mathcal{C})}{\delta^2}, \end{align*} for a fixed numerical constant $c$ (in fact I think $c$ is at most $9$). Here $\omega(\mathcal{C})$ is the Gaussian width defined as \begin{align*} \omega(\mathcal{C})=\mathbb{E}\big[\sup_{\mathbf{y}\in\mathcal{C}}\mathbf{g}^T\mathbf{y}\big], \end{align*} with $\mathbf{g}$ is a random Gaussian vector $\mathcal{N}(\mathbf{0},\mathbf{I})$. With this introduction here is my question. I want a similar result to hold about \begin{align*} \underset{\mathbf{y}\in\mathcal{C}}{\sup}\bigg|\frac{1}{m}\sum_{k=1}^m f(\mathbf{a}_k^T\mathbf{y})-E_{\mathbf{g}}[f(\mathbf{g}^T\mathbf{y})]\bigg|\le \delta, \end{align*} with $\mathbf{g}$ is a random Gaussian vector $\mathcal{N}(\mathbf{0},\mathbf{I})$. The only change is replacing $f(x)=x^2$ in Gordon's result with a general $f$. Obviously this is not true in general but assume that the function $f$ is bounded or its Lipschitz is the results above still true with with high probability as long as \begin{align*} m\ge c\frac{\omega^2(\mathcal{C})}{\delta^2}, \end{align*} with $c$ a constant that only depends on properties of the function $f$ e.g. bound, Lipschitz constant etc.

$\endgroup$
4
  • 1
    $\begingroup$ You can certainly get bounds on the quantity you're interested in (in the bounded case, see Talagrand's concentration inequality for empirical processes). But $\omega^2(\mathcal{C})$ is not the right bound for the sample size. For example, in Gordon's lemma there is a homogeneity that is not present when you have an arbitrary function. $\endgroup$
    – Joe Neeman
    Jun 17, 2016 at 19:34
  • $\begingroup$ Thanks your comment was very useful. I some how did not think in terms of Talagrand's concentration result. I have a few followup questions. I'm looking at his result through Massart's paper Theorem 4 "About the Constants in Talagrand's Concentration Inequalities for Empirical Processes". Do you by any chance know how crucial is the countable assumption? This theorem is useful for the bounded version case but I can't apply it to the above because of the countable $\mathcal{F}$ assumption. $\endgroup$
    – mohi
    Jun 19, 2016 at 1:07
  • $\begingroup$ Another question: Do you know what is the most general class of functions for which a Gordon type result holds (I actually realized this is easy when the function is Lipschitz by just applying symmetrization+comparison inequality) $\endgroup$
    – mohi
    Jun 19, 2016 at 1:11
  • 1
    $\begingroup$ The countable assumption isn't very important, since unless $f$ is extremely pathological you can just replace $\mathcal{C}$ by a countable, dense subset and the supremum will be the same. In general, the countable assumption is just there to ensure that the supremum is measurable. $\endgroup$
    – Joe Neeman
    Jun 20, 2016 at 10:24

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.