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.

  • 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 '16 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 '16 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 '16 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 '16 at 10:24

Your Answer

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

Browse other questions tagged or ask your own question.