Nemirovski's Inequalities Revisited

Introduction.

Our starting point is the following well known theorem from probability: Let $X_{1},\ldots,X_{n}$ be (stochastically) independent random variables with finite second moments, and let $S_{n}=\sum_{i=1}^{n}X_{i}$. Then

If we suppose that each $X_{i}$ has mean zero, $\mathop{\rm I\!E}\nolimits X_{i}=0$, then (1) becomes

An obvious question is how the exponent $r$ and the dimension $d$ enter an inequality of type (4). The influence of the dimension $d$ is crucial, since current statistical research often involves small or moderate “sample size” $n$ (the number of independent units), say on the order of $10^{2}$ or $10^{4}$, while the number $d$ of items measured for each independent unit is large, say on the order of $10^{6}$ or $10^{7}$. The following two examples for the random vectors $X_{i}$ provide lower bounds for the constant $K$ in (4):

But it is well-known that $\max_{1\leq j\leq d}|Z_{j}|=\sqrt{2\log d}+o_{p}(1)$ as $d\to\infty$. Thus candidates $K(d)$ for the constant in (4) have to satisfy

At least three different methods have been developed to prove inequalities of the form given by (4). The three approaches known to us are:

(a) deterministic inequalities for norms; (b) probabilistic methods for Banach spaces; (c) empirical process methods.

Nemirovski’s approach: Deterministic inequalities for norms.

Example 1.1 shows that this constant $\widetilde{K}(d,r)$ is indeed optimal for $1\leq r\leq 2$.

A refinement for r>2r>2.

In what follows we shall replace $\widetilde{K}(d,r)=d^{1-2/r}$ with substantially smaller constants. The main ingredient is the following result:

and stated Lemma 2.1 with the factor $r-1$ on the right side replaced with $Cr$ for some (absolute) constant $C>1$. Lemma 2.1, which is a special case of the more general Lemma 2.4 in the next subsection, may be applied to the partial sums $S_{0}:=0$ and $S_{k}:=\sum_{i=1}^{k}X_{i}$, $1\leq k\leq n$, to show that for $2\leq r<\infty$,

and inductively we obtain a second candidate for $K$ in (4):

Finally, we apply (6) again: For $2\leq q\leq r\leq\infty$ with $q<\infty$,

This inequality entails our first ($q=2$) and second ($q=r<\infty$) preliminary result, and we arrive at the following refinement:

This constant $K_{\rm Nem}(d,r)$ satisfies the (in)equalities

Thus Example 1.2 entails that for large dimension $d$, the constants $K_{\rm Nem}(d,\infty)$ and $2e\log d-e$ are optimal up to a factor close to $e\ \dot{=}\ 2.7183$.

2 Arbitrary LrL_{r}-spaces

where two such functions are viewed as equivalent if they coincide almost everywhere with respect to $\mu$. In what follows we investigate the functional

Note that $V(\cdot)$ is convex; thus for fixed $f,g\in L_{r}(\mu)$, the function

This proves the lower bound in the following lemma. We will prove the upper bound in Section 6 by computation of $v^{\prime\prime}$ and application of Hölder’s inequality.

Let $r\geq 2$. Then for arbitrary $f,g\in L_{r}(\mu)$,

In case of $r=2$, Lemma 2.4 is well known and easily verified. Here the upper bound for $V(f+g)$ is even an equality, i.e.

Lemma 2.4 improves on an inequality of . After writing this paper we realized Lemma 2.4 is also proved by ; see his (2.2) and Proposition 2.1, page 1680.

Lemma 2.4 leads directly to the following result:

3 A connection to geometrical functional analysis

The probabilistic approach: Type and co-type inequalities.

One of the basic results concerning Banach spaces with type $p$ and cotype $q$ is the following proposition:

As shown in , page 27, the Banach space $L_{r}(\mu)$ with $1\leq r<\infty$ (cf. section 2.2) is of type $\min(r,2)$. Similarly, $L_{r}(\mu)$ is co-type $\max(r,2)$. In case of $r\geq 2=p$, explicit values for the constant $T_{p}$ in Proposition 3.1 can be obtained from the optimal constants in Khintchine’s inequalities due to .

For $2\leq r<\infty$, the space $L_{r}(\mu)$ is of type $2$ with constant $T_{2}=B_{r}$, where

Thus for large values $r$, the conclusion of Corollary 3.3 is weaker than the one of Corollary 2.8.

At the heart of these tail bounds is the following exponential moment bound:

From the latter bound we shall deduce the following type inequality in Section 6:

Using this upper bound together with Proposition 3.1 yields another Nemirovski type inequality:

The constants $c_{d}$ can be expressed or bounded in terms of the distribution function $\Phi$ of $N(0,1)$, i.e. $\Phi(z)=\int_{-\infty}^{z}\phi(x)\,dx$ with $\phi(x)=\exp(-x^{2}/2)/\sqrt{2\pi}$. Namely, with $W:=\max_{1\leq j\leq d}|Z_{j}|$,

These considerations and various bounds for $\Phi$ will allow us to derive explicit bounds for $c_{d}$.

On the other hand, Hoeffding’s inequality (7) has been refined by Pinelis as follows:

where $h_{2}(d)\leq 3$, $h_{2}(d)$ becomes negative for $d>4.13795\times 10^{10}$, $h_{3}(d)$ becomes negative for $d\geq 14$, and $h_{j}(d)\sim-\log\log d$ as $d\rightarrow\infty$ for $j=1,2,3$.

In particular, one could replace $K_{\rm Type2}(d,\infty)$ in Corollary 3.5 with $8\log d+4h_{2}(d)$.

The empirical process approach: Truncation and Bernstein’s inequality.

An alternative to Hoeffding’s exponential tail inequality (7) is a classical exponential bound due to Bernstein (see e.g. ): Let $Y_{1},Y_{2},\ldots,Y_{n}$ be independent random variables with mean zero such that $|Y_{i}|\leq\kappa$. Then for any $v^{2}\geq\sum_{i=1}^{n}\mathop{\rm Var}\nolimits(Y_{i})$,

We will not use this inequality itself but rather an exponential moment inequality underlying its proof:

Let $Y$ be a random variable with mean zero and variance $\sigma^{2}$ such that $|Y|\leq\kappa$. Then for any $L>0$,

With the latter exponential moment bound we can prove a moment inequality for random vectors with bounded components:

Suppose that $X_{i}=(X_{i,j})_{j=1}^{d}$ satisfies $\|X_{i}\|_{\infty}\leq\kappa$, and let $\Gamma$ be an upper bound for $\max_{1\leq j\leq d}\sum_{i=1}^{n}\mathop{\rm Var}\nolimits(X_{i,j})$. Then for any $L>0$,

for some constant $\kappa_{o}>0$ to be specified later. Then we write $S_{n}=A_{n}+B_{n}$ with the centered random sums

The sum $A_{n}$ involves centered random vectors in $[-2\kappa_{o},2\kappa_{o}]^{d}$ and will be treated by means of Lemma 4.2, while $B_{n}$ will be bounded with elementary methods. Choosing the threshold $\kappa$ and the parameter $L$ carefully yields the following theorem.

If the random vectors $X_{i}$ are symmetrically distributed around $0$, one may even set

Comparisons.

The random vectors $X_{i}$ are independent with $\mathop{\rm I\!E}\nolimits\|X_{i}\|_{\infty}^{2}<\infty$ for all $i$.

In addition, $\mathop{\rm I\!E}\nolimits X_{i}=0$ for all $i$.

In addition, $X_{i}$ is symmetrically distributed around $0$ for all $i$.

In view of the general case, we reformulate inequality (4) as follows:

One reason for this extension is that in some applications, particularly in connection with empirical processes, it is easier and more natural to work with uncentered summands $X_{i}$. Let us discuss briefly the consequences of this extension in the three frameworks:

Between the centered and symmetric case there is no difference. If (4) holds in the centered case for some $K$, then in the general case

The latter inequality follows from the general fact that

If we set $p=1-d^{-1/2}$ for $d\geq 4$, then the latter ratio converges to $4$ as $d\to\infty$.

The approach via Rademacher type 2 inequalities:

The first part of Proposition 3.1, involving the Rademacher type constant $T_{p}$, remains valid if we drop the assumption that $\mathop{\rm I\!E}\nolimits X_{i}=0$ and replace $S_{n}$ with $S_{n}-\mathop{\rm I\!E}\nolimits S_{n}$. Thus there is no difference between the general and the centered case. In the symmetric case, however, the factor $2^{p}$ in Proposition 3.1 becomes superfluous. Thus, if (4) holds with a certain constant $K$ in the general and centered case, we may replace $K$ with $K/4$ in the symmetric case.

The approach via truncation and Bernstein’s inequality:

Our proof for the centered case does not utilize that $\mathop{\rm I\!E}\nolimits X_{i}=0$, so again there is no difference between the centered and general case. However, in the symmetric case, the truncated random vectors $1\{\|X_{i}\|_{\infty}\leq\kappa\}X_{i}$ and $1\{\|X_{i}\|_{\infty}>\kappa\}X_{i}$ are centered, too, which leads to the substantially smaller constant $K$ in Theorem 4.3.

Summaries and comparisons.

Table 1 summarizes the constants $K=K(d,\infty)$ we have found so far by the three different methods and for the three different cases. Table 2 contains the corresponding limits

Interestingly, there is no global winner among the three methods. But for the centered case, Nemirovski’s approach yields asymptotically the smallest constants. In particular,

The conclusion at this point seems to be that Nemirovski’s approach and the type 2 inequalities yield better constants than Bernstein’s inequality and truncation. Figure 1 shows the constants $K(d,\infty)$ for the centered case over a certain range of dimensions $d$.

Proofs.

In case of $r=\infty$, the asserted inequalities read

and are rather obvious. For $1\leq q<r<\infty$, (6) is an easy consequence of Hölder’s inequality. $\Box$

Proof of Lemma 2.4.

In case of $r=2$, $V(f+g)$ is equal to $V(f)+DV(f,g)+V(g)$. In case of $r\geq 2$ and $\|f\|_{r}=0$, both $DV(f,g)$ and $\int h(f)g\,d\mu$ are equal to zero, and the asserted inequalities reduce to the trivial statement that $V(g)\leq(r-1)V(g)$. Thus let us restrict our attention to the case $r>2$ and $\|f\|_{r}>0$.

is pointwise twice continuously differentiable with derivatives

By means of the inequality $|x+y|^{b}\leq 2^{b-1}\bigl(|x|^{b}+|y|^{b}\bigr)$ for real numbers $x$, $y$ and $b\geq 1$, a consequence of Jensen’s inequality, we can conclude that for any bound $t_{o}>0$,

The latter two envelope functions belong to $L_{1}(\mu)$. This follows from Hölder’s inequality which we rephrase for our purposes in the form

Hence we may conclude via dominated convergence that

is twice continuously differentiable with derivatives

is continuously differentiable with derivative

by virtue of Hölder’s inequality (17) with $\lambda=2/r$. Consequently, by using

Proof of Theorem 2.2.

The first part is an immediate consequence of the considerations preceding the theorem. It remains to prove the (in)equalities and expansion for $K_{\rm Nem}(d,r)$. Note that $K_{\rm Nem}(d,r)$ is the infimum of $h(q)d^{-2/r}$ over all real $q\in[2,r]$, where $h(q):=(q-1)d^{2/q}$ satisfies the equation

Since $7<e^{2}<8$, this shows that $h$ is strictly increasing on $[2,\infty)$ if $d\leq 7$. Hence

For $d\geq 8$, one can easily show that $\log d-\sqrt{(\log d-2)\log d}<2$, so that $h$ is strictly decreasing on $[2,r_{d}]$ and strictly increasing on $[r_{d},\infty)$, where

Moreover, one can verify numerically that $K_{\rm Nem}(d,r)\leq d\leq 2e\log d-e$ for $3\leq d\leq 7$.

Finally, for $d\geq 8$, the inequalities $r_{d}^{\prime}:=2\log d-2<r_{d}<r_{d}^{\prime\prime}:=2\log d$ yield

and for $1\leq d\leq 7$, the inequality $d=K_{\rm Nem}(d,\infty)\geq 2e\log(d)-3e$ is easily verified. $\Box$

2 Proofs for Section 3

The following proof is standard; see e.g. , page 160, , page 247. Let $x_{1},\ldots,x_{n}$ be fixed functions in $L_{r}(\mu)$. Then by , for any $t\in T$,

To use inequality (18) for finding an upper bound for the type constant for $L_{r}$, rewrite it as

It follows from Fubini’s theorem and the previous inequality that

Using the triangle inequality (or Minkowski’s inequality), we obtain

Furthermore, since $g(v)=v^{2/r}$ is a concave function of $v\geq 0$, the last display implies that

Proof of Lemma 3.4.

To this end note first that $h:[0,\infty)\to[1,\infty)$ with $h(t):=\cosh(t^{1/2})=\sum_{k=0}^{\infty}t^{k}/(2k)!$ is bijective, increasing and convex. Hence its inverse function $h^{-1}:[1,\infty)\to[0,\infty)$ is increasing and concave, and one easily verifies that $h^{-1}(s)=\bigl(\log(s+(s^{2}-1)^{1/2})\bigr)^{2}\leq(\log(2s))^{2}$. Thus it follows from Jensen’s inequality that for arbitrary $t>0$,

Now the assertion follows if we set $t=\sqrt{2\log(2d)/v^{2}}$. $\Box$

Proof of (9).

We may replace the random sequence $\{X_{i}\}$ in Example 1.2 with the random sequence $\{\epsilon_{i}X_{i}\}$, where $\{\epsilon_{i}\}$ is a Rademacher sequence independent of $\{X_{i}\}$. Thereafter we condition on $\{X_{i}\}$, i.e. we view it as a deterministic sequence such that $n^{-1}\sum_{i=1}^{n}X_{i}X_{i}^{\top}$ converges to the identity matrix $I_{d}$ as $n\to\infty$, by the strong law of large numbers. Now Lindeberg’s version of the multivariate Central Limit Theorem shows that

Inequalities for Φ\Phi.

The subsequent results will rely on (10) and several inequalities for $1-\Phi(z)$. The first of these is:

which is known as Mills’ ratio; see and for related results. The proof of this upper bound is easy: Since $\phi^{\prime}(z)=-z\phi(z)$ it follows that

A very useful pair of upper and lower bounds for $1-\Phi(z)$ are as follows:

the inequality on the left is due to Komatsu (see e.g. p. 17), while the inequality on the right is an improvement of an earlier result of Komatsu due to .

Proof of Lemma 3.6.

Now by (10) with $v^{2}$ and $v_{m}^{2}$ as in the proof of Lemma 3.4, followed by Mills’ ratio (19),

Now instead of the Mills’ ratio bound (19) for the tail of the normal distribution, we use the upper bound part of (21) due to . This yields

where we have defined $c:=4K/\sqrt{2\pi}=12.88/\sqrt{2\pi}$, and hence

where it is easily checked that $h_{2}(d)\leq 3$ for all $d\geq 1$. Moreover $h_{2}(d)$ is negative for $d>4.13795*10^{10}$. This completes the proof of the upper bound in (3.6).

To prove the lower bound for $c_{d}$ in (3.6), we use the lower bound of , Lemma 6.9, page 157 (which is, in this form, due to ). This yields

for any $t_{o}>0$, where $\lambda=2d(1-\Phi(t_{o}))$. By using Komatsu’s lower bound (21), we find that

Now we let $c\equiv\sqrt{2/\pi}$ and $\delta>0$ and choose

For this choice we see that $t_{o}\rightarrow\infty$ as $d\rightarrow\infty$,

as $d\to\infty$, so the first term on the RHS of (24) converges to $1$ as $d\rightarrow\infty$, and it can be rewritten as

To prove the upper bounds for $c_{d}$, we will use the upper bound of , Lemma 6.9, page 157 (which is, in this form, due to ). For every $t_{o}>0$

Evaluating this bound at $t_{o}=\sqrt{2\log(d/\sqrt{2\pi})}$ and then using Mills’ ratio again yields

and hence if $d\geq 27>e^{3.28735...}\ \dot{=}\ 26.77$. The claimed inequality is easily verified numerically for $d=3,\ldots,26$. (It fails for $d=2$.) As can be seen from (25), $2\log d-\log(2\pi)$ gives a reasonable approximation to $\mathop{\rm I\!E}\nolimits\max_{1\leq j\leq d}Z_{j}^{2}$ for large $d$. Using the upper bound in (21) instead of the second application of Mills’ ratio and choosing $t_{o}^{2}=2\log(cd/\sqrt{2\log(cd)})$ with $c\ :=\ \sqrt{2/\pi}$ yields the third bound for $c_{d}$ in (3.6) with

3 Proofs for Section 4

It follows from $\mathop{\rm I\!E}\nolimits Z=0$, the Taylor expansion of the exponential function and the inequality $\mathop{\rm I\!E}\nolimits|Z|^{m}\leq\sigma^{2}\kappa^{m-2}$ for $m\geq 2$ that

Proof of Lemma 4.2.

Applying Lemma 4.1 to the $j$-th components $X_{i,j}$ of $X_{i}$ and $S_{n,j}$ of $S_{n}$ yields for all $L>0$,

As in the proof of Lemma 3.4 we conclude that

which is equivalent to the inequality stated in the lemma. $\Box$

Proof of Theorem 4.3.

For fixed $\kappa_{o}>0$ we split $S_{n}$ into $A_{n}+B_{n}$ as described before. Let us bound the sum $B_{n}$ first: For this term we have

Therefore, since $\mathop{\rm I\!E}\nolimits B_{n1}=0$,

where we define $\Gamma:=\sum_{i=1}^{n}\mathop{\rm I\!E}\nolimits\|X_{i}\|_{\infty}^{2}$.

The first sum, $A_{n}$, may be bounded by means of Lemma 4.2 with $\kappa=2\kappa_{o}$, utilizing the bound

where $\alpha:=2L\log(2d)$ and $\beta:=\Gamma(L\,{\rm e}(L)+4)/2$. This bound is minimized if $\kappa_{o}=\sqrt{\beta/\alpha}$ with minimum value

and for $L=0.407$ the latter bound is not greater than

In the special case of symmetrically distributed random vectors $X_{i}$, our treatment of the sum $B_{n}$ does not change, but in the bound for $\mathop{\rm I\!E}\nolimits\|A_{n}\|_{\infty}^{2}$ one may replace $2\kappa_{o}$ with $\kappa_{o}$, because $\mathop{\rm I\!E}\nolimits X_{i}^{(a)}=0$. Thus

For $L=0.5$ the latter bound is not greater than

Acknowledgements.

The authors owe thanks to the referees for a number of suggestions which resulted in a considerable improvement in the article. The authors are also grateful to Ilya Molchanov for drawing their attention to Banach-Mazur distances, and to Stanislaw Kwapien and Vladimir Koltchinskii for pointers concerning type and co-type proofs and constants. This research was initiated during the opening week of the program on “Statistical Theory and Methods for Complex, High-Dimensional Data” held at the Isaac Newton Institute for Mathematical Sciences from 7 January to 27 June, 2008, and was made possible in part by the support of the Isaac Newton Institute for visits of various periods by Dümbgen, van de Geer, and Wellner. The research of Wellner was also supported in part by NSF grants DMS-0503822 and DMS-0804587. The research of Dümbgen and van de Geer was supported in part by the Swiss National Science Foundation.

References