Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am reading a paper and stuck with an inequality used in that paper.

$\varepsilon^n=(\varepsilon_1^n, \varepsilon_2^n,\ldots,\varepsilon_n^n)^T$ is a vector of i.i.d. random variables with mean 0 and variance $\sigma^2$. Assume that $\varepsilon_i^n$ have finite $2k$'th moment $E(\varepsilon_i^n)^{2k}<\infty$ for an integer $k>0$. Show that for a constant $n$-dimensional vector $\alpha$, have

$$E(\alpha^T\varepsilon^n)^{2k}\leq (2k-1)!!\|\alpha\|_2^2E(\varepsilon_i^n)^{2k}.$$

The paper I am reading is "On Model Selection Consistency of Lasso" by Zhao and Yu 2006, which can be found via http://jmlr.csail.mit.edu/papers/volume7/zhao06a/zhao06a.pdf and the inequality appears on Page 2558.

Thanks

share|improve this question

1 Answer 1

up vote 4 down vote accepted

As observed in a (now deleted) previous comment, the exponent of $\|\alpha\|_2$ should be $2k$ instead of $2$ for homogeneity reasons.

If the $\varepsilon_i$ are symmetric, then this can be proven by a variant of the exponential moment generating function method used to prove Khintchine's inequality. Indeed, if we normalise ${\bf E} \varepsilon_i^{2k}$ to be 1, then from Holder's inequality we see that ${\bf E} \varepsilon_i^j$ vanishes for odd $j$ and is bounded by $1$ for even $j$ up to $2k$. In particular, the exponential moment generating function

$$ {\bf E} \exp( t \varepsilon_i ) = \sum_{j=0}^\infty \frac{t^j}{j!} {\bf E} \varepsilon_i^j$$

is dominated by $\cosh( t^2 )$ in the sense that the coefficients of the former power series up to $t^{2k}$ are bounded in magnitude by those of the latter. $\cos(t^2)$ is dominated in turn by $\exp(t^2/2)$. Since

$$ {\bf E} \exp( t \varepsilon ) = \prod_{i=1}^n {\bf E} \exp(\alpha_i t \varepsilon_i )$$

we conclude that ${\bf E} \exp( t \varepsilon )$ is dominated by $\exp( \|\alpha\|_2^2 t^2 / 2)$. Extracting the $t^{2k}$ coefficient gives the claim.

The situation seems to be more subtle in the non-symmetric case; there does not seem to be a similarly simple argument (though one can certainly obtain a bound with $(2k-1)!!$ replaced by some weaker constant $C_k$ depending on $k$). It might be that the authors overlooked or neglected to mention a symmetry hypothesis when using this result.

share|improve this answer
    
Thank you! It's clear and helpful. –  Dennis Jan 14 '13 at 2:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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