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.



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.

| cite | improve this answer | |

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.