Dvoretzky's Theorem and Almost Euclidean Sections

Why This Matters

The cube $B_\infty^n = [-1,1]^n$ is far from round. It contains the Euclidean ball and sits inside the ball of radius $\sqrt{n}$, and $\sqrt{n}$ is the best constant:

$$B_2^n \subset B_\infty^n \subset \sqrt{n}\, B_2^n .$$

Yet the cube has central sections of dimension proportional to $\log n$ that are round up to a factor $1+\varepsilon$. Dvoretzky's theorem says the same holds for every symmetric convex body in $\mathbb{R}^n$, equivalently for every $n$-dimensional normed space. High dimension forces Euclidean structure to appear somewhere.

The proof in current use is Milman's 1971 argument, and it is the same three-step argument that proves the Johnson-Lindenstrauss lemma: concentration of a Lipschitz function on the sphere, an epsilon-net, and a union bound. What changes is the object. JL keeps the pairwise distances of a finite point set; Dvoretzky finds a subspace on which an arbitrary norm is almost a multiple of the Euclidean norm.

The quantity that sets the dimension is the mean of the norm over the sphere divided by its Lipschitz constant. For a norm given as a supremum of linear functionals over a set $T$, that mean is the Gaussian width of $T$ divided by $\mathbb{E}\|g\|_2 \approx \sqrt{n}$, and the Gaussian width is the quantity that appears as Gaussian complexity in empirical process bounds.

Watch Out

Not the Dvoretzky-Kiefer-Wolfowitz inequality

The name appears on two unrelated results. The Dvoretzky-Kiefer-Wolfowitz (DKW) inequality (1956) is a tail bound for the empirical CDF: with the sharp constant of Massart (1990), $\mathbb{P}(\sup_x |F_n(x) - F(x)| > \epsilon) \le 2e^{-2n\epsilon^2}$, where $n$ is a sample size. Dvoretzky's theorem (1961) is a statement about subspaces of normed spaces with no probability model in the hypothesis; there $n$ is a dimension and $\varepsilon$ is a geometric distortion. Probability enters only through the proof.

Mental Model

Fix a norm $\|\cdot\|$ on $\mathbb{R}^n$ and look at its values on the Euclidean unit sphere.

1. Concentration. A point drawn uniformly from $S^{n-1}$ has norm close to the average value $M$, with fluctuations of order $b/\sqrt{n}$, where $b$ is the Lipschitz constant of the norm.
2. Discretization. A $k$-dimensional subspace is determined, up to a small error, by its values on a net of $(9/\varepsilon)^k$ points of its unit sphere.
3. Union bound. Rotate a fixed $k$-dimensional subspace at random. Each net point lands on a uniform point of $S^{n-1}$, so each fails with probability about $\exp(-c\varepsilon^2 n (M/b)^2)$. The union bound succeeds while $k\log(9/\varepsilon)$ stays below a small multiple of $\varepsilon^2 n (M/b)^2$.

So the dimension budget is $n(M/b)^2$. The remaining work is showing that this budget is at least of order $\log n$ after a suitable linear change of coordinates, and that it is also an upper limit for random subspaces.

Setup and Notation

Throughout, $n$ is the ambient dimension, following the Dvoretzky literature. On the measure concentration page the dimension is $d$ and $n$ counts points in the JL lemma.

Definition

Mean and Lipschitz constant of a norm$M,b$

Let $\|\cdot\|$ be a norm on $\mathbb{R}^n$, $\|\cdot\|_2$ the Euclidean norm, $S^{n-1}$ the Euclidean unit sphere, and $\sigma$ the rotation-invariant probability measure on $S^{n-1}$. Define

$$b = \max_{\theta \in S^{n-1}} \|\theta\|, \qquad M = \int_{S^{n-1}} \|\theta\| \, d\sigma(\theta).$$

Then $\|x\| \le b\|x\|_2$ for every $x$, so $\bigl|\|x\| - \|y\|\bigr| \le \|x-y\| \le b\|x-y\|_2$ and the norm is $b$-Lipschitz on the sphere. Also $M \le b$. The unit ball $K = \{x : \|x\| \le 1\}$ is a symmetric convex body, and every symmetric convex body with nonempty interior is the unit ball of the norm $\|x\|_K = \inf\{\lambda > 0 : x \in \lambda K\}$.

Definition

(1+epsilon)-Euclidean subspace$r\Vert x{\Vert }_2\le \Vert x\Vert \le (1+\epsilon )r\Vert x{\Vert }_2$

A linear subspace $E \subseteq \mathbb{R}^n$ is $(1+\varepsilon)$-Euclidean for $\|\cdot\|$ when there is $r > 0$ with

$$r\|x\|_2 \le \|x\| \le (1+\varepsilon)\, r\,\|x\|_2 \quad \text{for all } x \in E.$$

In terms of the unit ball, the section $K \cap E$ lies between two Euclidean balls of $E$ whose radii differ by the factor $1+\varepsilon$. A two-sided estimate $(1-\varepsilon)M\|x\|_2 \le \|x\| \le (1+\varepsilon)M\|x\|_2$ gives the factor $(1+\varepsilon)/(1-\varepsilon)$, which is at most $1+3\varepsilon$ when $\varepsilon \le 1/3$. Running such an estimate with $\varepsilon/3$ in place of $\varepsilon$ therefore gives a $(1+\varepsilon)$-Euclidean subspace.

Definition

Critical dimension$k(X)=n(M/b{)}^2$

For $X = (\mathbb{R}^n, \|\cdot\|)$ the critical dimension is $k(X) = n(M/b)^2$. It satisfies $2/\pi \le k(X) \le n$, with $k(X) = n$ for the Euclidean norm. A random $k$-dimensional subspace means $E = U E_0$ for a fixed $k$-dimensional $E_0$ and $U$ drawn from the Haar probability measure on the orthogonal group $O(n)$. For each fixed unit vector $\theta$, the vector $U\theta$ is uniform on $S^{n-1}$. Huang and Wei reserve the name Dvoretzky dimension for the largest $k$ at which a random $k$-dimensional section is almost spherical with probability above $1/2$; their Theorem B shows that it lies between $\bar{C}_\varepsilon\, k(X)$ and $C\, k(X)$, with $C$ universal and $\bar{C}_\varepsilon$ depending only on $\varepsilon$.

The lower bound $k(X) \ge 2/\pi$ is Exercise 3 below.

Dvoretzky's Theorem

Theorem

Dvoretzky's Theorem (with Milman's log n dimension)

Statement

For every $\varepsilon \in (0,1)$ there is $c(\varepsilon) > 0$ such that every normed space $(\mathbb{R}^n, \|\cdot\|)$ has a $(1+\varepsilon)$-Euclidean subspace of dimension

$$k \ge c(\varepsilon) \log n .$$

Equivalently, every symmetric convex body $K \subset \mathbb{R}^n$ has a $k$-dimensional subspace $E$ and $r > 0$ with

$$r\,(B_2^n \cap E) \subseteq K \cap E \subseteq (1+\varepsilon)\, r\,(B_2^n \cap E).$$

Intuition

The theorem does not say that a random subspace works for every body in its given coordinates. It says a good subspace exists. The proof first moves $K$ to a position where the Euclidean ball is the ellipsoid of largest volume inside $K$. In that position $b \le 1$ and the mean $M$ is at least of order $\sqrt{\log n / n}$, so the critical dimension $n(M/b)^2$ is at least of order $\log n$, and random subspaces of that dimension work.

Proof Sketch

History. Dvoretzky proved that the dimension $k(\varepsilon, n)$ tends to infinity with $n$ for each fixed $\varepsilon$, answering a question of Grothendieck. Milman gave the concentration-of-measure proof and was the first to obtain the order $\log n$ (Schechtman's lecture notes, Theorems 1.1 and 1.2).

Position. Changing $K$ to $TK$ for an invertible linear $T$ does not change the problem: an almost Euclidean section of $TK$ is an almost ellipsoidal section of $K$, and a $k$-dimensional ellipsoid has a Euclidean section of dimension $k/2$. So assume $B_2^n$ is the ellipsoid of maximal volume inside $K$. Then $b \le 1$.

Lower bound on the mean. A weak form of the Dvoretzky-Rogers lemma gives an orthonormal basis $x_1, \ldots, x_n$ with $\|x_i\| \ge (2e)^{-1}$ for $i \le n/2$. Averaging over sign changes of the coordinates gives

$$M \ge \frac{1}{2e}\int_{S^{n-1}} \max_{i \le n/2} |\theta_i| \, d\sigma(\theta) = \frac{1}{2e}\,\frac{\mathbb{E}\max_{i \le n/2} |g_i|}{\mathbb{E}\|g\|_2},$$

with $g$ a standard Gaussian vector. The numerator is of order $\sqrt{\log n}$ and the denominator is at most $\sqrt{n}$, so $M \ge c\sqrt{\log n / n}$ and $n(M/b)^2 \ge c^2 \log n$.

Conclude. Apply Milman's theorem below with $k$ of order $\varepsilon^2 \log n / \log(9/\varepsilon)$, or of order $\varepsilon^2 \log n$ with Gordon's improvement.

Why It Matters

Any finite-dimensional normed space, however far from Euclidean, contains a Euclidean piece whose dimension grows with $n$. This is the starting point of the local theory of normed spaces. The random form of the proof is also the reason the geometry of a norm on most low-dimensional subspaces is a scaled Euclidean geometry.

Failure Mode

The order $\log n$ cannot be improved. For $\ell_\infty^n$, if $\ell_2^k$ embeds into $\ell_\infty^n$ with distortion $C$, then $k \le A C^2 \log n$ for an absolute constant $A$ (Schechtman's notes, remark after Proposition 3.1, using Bennett, Dor, Goodman, Johnson and Newman). The theorem is existential: the proof is probabilistic and does not produce a specific subspace. The constant $c(\varepsilon)$ must tend to zero: a $(1+\varepsilon)$-Euclidean subspace of $\ell_\infty^n$ has dimension at most $C\log n / \log(1/(c\varepsilon))$ (Claim 3.3 of the same notes).

report a correction →

Milman's Theorem: Random Subspaces up to the Critical Dimension

Theorem

Milman's Random Form of Dvoretzky's Theorem

Statement

There is a universal constant $c > 0$ such that for every $n$, every norm on $\mathbb{R}^n$, every $\varepsilon \in (0,1)$ and every integer $k \ge 1$ with

$$k \le \frac{c\,\varepsilon^2}{\log(9/\varepsilon)}\; n\left(\frac{M}{b}\right)^2,$$

a random $k$-dimensional subspace $E$ satisfies, with probability at least $1 - 4\exp\bigl(-c\,\varepsilon^2 n (M/b)^2\bigr)$,

$$(1-\varepsilon)\,M\,\|x\|_2 \;\le\; \|x\| \;\le\; (1+\varepsilon)\,M\,\|x\|_2 \qquad \text{for all } x \in E.$$

Improvement. The factor $\log(9/\varepsilon)$ is an artifact of the net argument. Gordon (1985) proved that $k \le c\,\varepsilon^2 n (M/b)^2$ suffices, and Schechtman (1989) gave a second proof closer to Milman's argument.

Intuition

Concentration on the sphere says a $b$-Lipschitz function deviates from its mean by $\delta M$ with probability at most about $\exp(-c\,\delta^2 n M^2 / b^2)$. A $k$-dimensional subspace needs about $(9/\varepsilon)^k$ such events to hold at once. Setting the union bound against the tail gives $k \log(9/\varepsilon) \lesssim \varepsilon^2 n (M/b)^2$. The ratio $M/b$ is scale-free, so the dimension depends on the shape of the unit ball only.

Proof Sketch

Step 1 (concentration). For a $b$-Lipschitz $f$ on $S^{n-1}$ and $t > 0$,

$$\sigma\bigl(\{\theta : |f(\theta) - \mathbb{E} f| \ge bt\}\bigr) \le 4\exp(-c_0 t^2 n)$$

for a universal $c_0 > 0$ (the form quoted by Huang and Wei, Theorem 2; the site's Levy lemma uses the median and explicit constants). With $f = \|\cdot\|$, $t = \delta M / b$ and $\delta = \varepsilon/4$:

$$\sigma\bigl(\bigl|\|\theta\| - M\bigr| \ge \delta M\bigr) \le 4\exp\!\left(-\frac{c_0\,\varepsilon^2}{16}\, n\left(\frac{M}{b}\right)^2\right).$$

Step 2 (net). A maximal $\delta$-separated set $\mathcal{N}$ in the unit sphere of $E_0$ is a $\delta$-net, and the volume argument gives $|\mathcal{N}| \le (1 + 2/\delta)^k = (1 + 8/\varepsilon)^k \le (9/\varepsilon)^k$.

Step 3 (union bound). For Haar $U$, each $U\theta$ with $\theta \in \mathcal{N}$ is uniform on $S^{n-1}$. So all net points satisfy $(1-\delta)M \le \|U\theta\| \le (1+\delta)M$ except with probability

$$4\left(\frac{9}{\varepsilon}\right)^{k} \exp\!\left(-\frac{c_0\,\varepsilon^2}{16}\, n\left(\frac{M}{b}\right)^2\right) \le 4\exp\!\left(-\frac{c_0\,\varepsilon^2}{32}\, n\left(\frac{M}{b}\right)^2\right),$$

where the inequality uses $k\log(9/\varepsilon) \le \tfrac{c_0}{32}\varepsilon^2 n (M/b)^2$. Take $c = c_0/32$.

Step 4 (net to subspace). Let $A = \max\{\|Ux\| : x \in E_0,\ \|x\|_2 = 1\}$. For a unit $x \in E_0$ pick $\theta \in \mathcal{N}$ with $\|x - \theta\|_2 \le \delta$. Then $\|U(x-\theta)\| \le \delta A$, so $A \le (1+\delta)M + \delta A$, which gives $A \le \frac{1+\delta}{1-\delta}M \le (1 + \tfrac{8}{3}\delta)M$ for $\delta \le 1/4$. For the lower side, $\|Ux\| \ge (1-\delta)M - \delta A \ge (1 - \tfrac{8}{3}\delta)M$. With $\delta = \varepsilon/4$ both factors are within $\tfrac{2}{3}\varepsilon$ of $1$. The subspace $E = UE_0$ is uniformly distributed, and homogeneity extends the bound from unit vectors to all of $E$.

Why It Matters

The theorem turns a question about all subspaces into one number computed from the norm. For $\ell_1^n$ it gives almost Euclidean subspaces of dimension proportional to $n$; for $\ell_\infty^n$ it gives dimension of order $\log n$ (worked example below). With a Gaussian vector $G$ the same quantity reads $(\mathbb{E}\|G\|/b)^2$, which is how Tikhomirov (2018) states it: since $G = \|G\|_2 \cdot (G/\|G\|_2)$ with the two factors independent, $\mathbb{E}\|G\| = \mathbb{E}\|G\|_2 \cdot M$, and $(\mathbb{E}\|G\|_2)^2$ lies between $n-1$ and $n$.

Failure Mode

The ratio $M/b$ is not invariant under linear maps, so in bad coordinates the guarantee is weak even for ellipsoids. For $\|x\| = \bigl(R^2 x_1^2 + x_2^2 + \cdots + x_n^2\bigr)^{1/2}$ with $R$ large, $b = R$ while $M \le \sqrt{1 + R^2/n}$, so $n(M/b)^2 \le n/R^2 + 1$. The $\varepsilon^2$ dependence cannot be improved in this random form: Figiel's example in Schechtman's notes (Claim 3.2) is, for $n > \varepsilon^{-4}$, a norm between $\|\cdot\|_2$ and $2\|\cdot\|_2$ for which every subspace where the two norms are $(1+\varepsilon)$-equivalent has dimension at most $C\varepsilon^2 n$, while $n(M/b)^2 \ge n/4$.

report a correction →

The Critical Dimension Is Also an Upper Bound

Milman's theorem is a lower bound on how large random almost Euclidean subspaces can be. The matching upper bound says a random subspace of dimension much larger than $n(M/b)^2$ is not almost Euclidean.

Theorem

Upper Bound on the Dvoretzky Dimension

Statement

There is a universal constant $C$ such that the following holds for every $n$, every norm on $\mathbb{R}^n$ and every $\varepsilon \in (0,1)$. If a random $k$-dimensional subspace $E$ satisfies

$$(1-\varepsilon)M < \|x\| < (1+\varepsilon)M \quad \text{for all } x \in E \cap S^{n-1}$$

with probability greater than $1/2$, then $k < C\,n\,(M/b)^2$.

Together with Milman's theorem, the largest such $k$ lies between $c(\varepsilon)\,n(M/b)^2$ and $C\,n(M/b)^2$. Milman and Schechtman (1997) proved an upper bound of this order, with a probability threshold depending on $n$ and $k$, under the extra condition $M/b > c\sqrt{\log n / n}$; Huang and Wei (2017) gave the elementary proof sketched below, without that condition.

Intuition

One direction of the sphere already caps the dimension. The norm is largest, equal to $b$, in some direction $\theta_0$, so $\|x\| \ge b\,|\langle x, \theta_0\rangle|$. A $k$-dimensional subspace contains a unit vector whose inner product with $\theta_0$ is the length of the projection of $\theta_0$ onto it, about $\sqrt{k/n}$. That vector has norm at least about $b\sqrt{k/n}$, which must stay below $(1+\varepsilon)M$.

Proof Sketch

Pick $\theta_0 \in S^{n-1}$ with $\|\theta_0\| = b$. Since $\|x\| \le b\|x\|_2$, the ball $b^{-1}B_2^n$ lies in $K$ and touches $\partial K$ at $\theta_0/b$. A supporting hyperplane of $K$ at that point also supports the ball there, so it is $\{\langle x, \theta_0\rangle = 1/b\}$. By symmetry $K \subseteq \{|\langle x, \theta_0\rangle| \le 1/b\}$, which is the inequality $\|x\| \ge b|\langle x, \theta_0\rangle|$.

If $E$ is good, then $b\,\langle x, \theta_0\rangle < (1+\varepsilon)M$ for all unit $x \in E$, and the supremum of $\langle x, \theta_0\rangle$ over unit $x \in E$ is $\|P_E\theta_0\|_2$. So

$$\mathbb{P}(E \text{ good}) \le \mathbb{P}\!\left(\|P_E \theta_0\|_2 < (1+\varepsilon)\frac{M}{b}\right).$$

The random variable $\|P_E\theta_0\|_2$ has the law of $\|P_{E_0}\theta\|_2$ for $\theta$ uniform on $S^{n-1}$, a $1$-Lipschitz function with $\mathbb{E}\|P_{E_0}\theta\|_2^2 = k/n$. Concentration puts it near $\sqrt{k/n}$ at scale $1/\sqrt{n}$, so a probability above $1/2$ forces $\sqrt{k/n} \le C'(1+\varepsilon)M/b$ once $k$ exceeds an absolute constant. Since $1+\varepsilon < 2$ and $M/b \ge c/\sqrt{n}$, this gives $k < C n (M/b)^2$ in all cases.

Why It Matters

The formula $n(M/b)^2$ is the answer for random sections: it is both sufficient and necessary up to constants. For $\ell_1^n$ random sections at the scale $M$ stay almost Euclidean up to dimension of order $n$. For $\ell_\infty^n$ every almost Euclidean subspace, random or not, has dimension $O(\log n)$ by the failure mode of Dvoretzky's theorem above. The constant in the upper bound does not depend on $\varepsilon$; Huang and Wei show by example that it cannot be replaced by a quantity tending to zero with $\varepsilon$.

Failure Mode

The bound concerns random subspaces only. A special subspace can be far larger. For $\|x\| = \max\bigl(\|x\|_2,\ \sqrt{n}\,|x_1|\bigr)$ one has $b = \sqrt{n}$ and $M \le 1 + \sqrt{n}\,\mathbb{E}|\theta_1| < 3$, so $n(M/b)^2 < 9$, yet the hyperplane $\{x_1 = 0\}$ of dimension $n-1$ is exactly Euclidean. This gap between random and existential behavior is why Dvoretzky's theorem needs the change of position.

report a correction →

Worked Example: Three Norms

Use $\theta = g/\|g\|_2$ with $g$ standard Gaussian in $\mathbb{R}^n$; $\theta$ is uniform on $S^{n-1}$ and independent of $\|g\|_2$. Hence $\mathbb{E}\|g\| = \mathbb{E}\|g\|_2 \cdot M$ for any norm. Also $n - 1 \le (\mathbb{E}\|g\|_2)^2 \le n$: the upper bound is Jensen's inequality, and the lower bound follows from $\operatorname{Var}\|g\|_2 \le 1$, the Gaussian Poincare inequality for the 1-Lipschitz function $\|\cdot\|_2$.

$\ell_1^n$. Cauchy-Schwarz gives $\|x\|_1 \le \sqrt{n}\|x\|_2$ with equality at $(1,\ldots,1)/\sqrt{n}$, so $b = \sqrt{n}$. Also $\mathbb{E}\|g\|_1 = n\sqrt{2/\pi}$, so $M = n\sqrt{2/\pi}/\mathbb{E}\|g\|_2$ and $n(M/b)^2 = M^2 \ge 2n/\pi$. Random subspaces of dimension $c(\varepsilon) n$ are almost Euclidean.

$\ell_\infty^n$. Here $b = 1$, attained at a coordinate vector. The maximum of $|g_i|$ is a maximum of $2n$ standard Gaussians $\pm g_i$, so $\mathbb{E}\max_i |g_i| \le \sqrt{2\log(2n)}$, and it is also at least a constant times $\sqrt{\log n}$. Therefore $n M^2$ is of order $\log n$.

Numbers. At $n = 10^6$ the $\ell_1$ critical dimension is at least $2\cdot 10^6/\pi$, about 636,620, while the $\ell_\infty$ critical dimension is at most $2 \cdot 10^6 \log(2\cdot 10^6)/(10^6 - 1) \approx 29.0$. The constants $c(\varepsilon)$ are not explicit, so these numbers are the critical dimensions, not guaranteed values of $k$. For $2 < p < \infty$ the same computation gives dimension of order $n^{2/p}$ for $\ell_p^n$, and that order is also an upper bound for any Euclidean subspace (Schechtman's notes, Proposition 3.1).

The Dependence on Epsilon

The dependence of $k$ on $\varepsilon$ differs between the random theorem and the existential theorem.

Three points follow from the table.

• Random form. In the position where the Euclidean ball is the maximal volume ellipsoid, random subspaces of dimension $k \le c\,\varepsilon^2 \log n$ are $(1+\varepsilon)$-Euclidean with probability at least $1 - 2n^{-c\varepsilon^2}$, and Tikhomirov shows by example (his Proposition 2) that $\varepsilon^2\log n$ cannot be improved in that position.
• Existence beats randomness. Schechtman's 2006 argument combines Milman's theorem with the Alon-Milman theorem on subspaces isomorphic to $\ell_\infty^m$ and the cube estimate, and reaches $\varepsilon$ up to logarithmic factors.
• Open as of the 2012 notes. Schechtman's lecture notes (arXiv:1110.6401, revised July 2012) describe the exact $\varepsilon$ dependence in the existential theorem as open. Their Theorem 4.1 and the cube estimate of Claim 3.3 leave a gap between $\varepsilon/(\log(1/\varepsilon))^2$ and $1/\log(1/\varepsilon)$.

What Artstein, Milman and Szarek Proved

The paper "Duality of metric entropy" by S. Artstein, V. Milman and S. J. Szarek (Annals of Mathematics, 2004) works with the same objects as the Dvoretzky-Milman theory: mean widths of sections and Haar-random projections. Its main theorem is a duality statement for covering numbers. The paper does not state a Dvoretzky theorem or a new $\varepsilon$ dependence, and nothing on this page attributes one to it.

Definition

Half mean width$M^{\ast }(A)$

For a set $A \subset \mathbb{R}^n$, the paper uses

$$M^*(A) = \int_{S^{n-1}} \sup_{y \in A} \langle u, y\rangle \, d\sigma(u),$$

half the mean width of $A$. For a symmetric convex body $K$ the support function $\sup_{y \in K}\langle u, y\rangle$ equals the norm $\|u\|_{K^\circ}$ of the polar body $K^\circ = \{u : \sup_{x \in K}\langle x, u\rangle \le 1\}$. So $M^*(K)$ is the mean $M$ of the norm with unit ball $K^\circ$, and the maximum of that norm over the sphere is the circumradius $\max_{y\in K}\|y\|_2$. This identity follows from the definitions; it is the link between their parameter and the critical dimension on this page.

Write $N(K, T)$ for the least number of translates of $T$ needed to cover $K$, and $D = B_2^n$.

Theorem

Duality of Metric Entropy (Artstein, Milman, Szarek)

Statement

There are universal constants $\alpha$ and $\beta$ such that for every $n$ and every origin-symmetric convex body $K \subset \mathbb{R}^n$,

$$N(D, \alpha^{-1}K^\circ)^{1/\beta} \;\le\; N(K, D) \;\le\; N(D, \alpha K^\circ)^{\beta}.$$

Applying this to multiples of $K$ gives, for every $t > 0$,

$$\beta^{-1}\log N(D, \alpha^{-1} t K^\circ) \le \log N(K, tD) \le \beta \log N(D, \alpha t K^\circ).$$

The authors state right after Theorem 1 that their method gives $\beta = 2 + \varepsilon$ for any $\varepsilon > 0$, with $\alpha = \alpha(\varepsilon)$, and carry this out in Section 5; the scaled form above is their inequality (2).

Intuition

$\log N(K, tD)$ is the number of bits needed to describe $K$ at Euclidean resolution $t$. $\log N(D, tK^\circ)$ is the number of bits needed to describe the Euclidean ball at resolution $t$ in the dual norm $\|\cdot\|_{K^\circ}$. The theorem says these two complexity profiles agree at every scale, up to universal constants in the scale and in the exponent.

Proof Sketch

The paper proceeds in three steps, following its own outline.

1. Duality with a body-dependent constant. With $N(K,D) = 2^k$, set $\gamma(K) = \max\{1,\ M^*(K\cap D)\sqrt{n/k}\}$. Their Lemma 3 (combining earlier statements of Milman-Szarek and of the three authors) gives $N(K,D) \le N(D, \tfrac{c_2}{\gamma}K^\circ)^3$ and $N(D, C_2(\varepsilon)\gamma K^\circ) \le N(K,D)^{1+\varepsilon}$.
2. Reduction to few points. Observation 4 replaces $K$ by the convex hull of $N(K,D)$ points, and Proposition 5 gives $M^*(K\cap D) \le C_0(\log R)^3\sqrt{k/n}$ for such hulls inside $RD$, so $\gamma \le \max\{1, C_0(\log R)^3\}$.
3. Removing the radius. An iterating procedure over an increasing sequence of radii (Lemma 7) bounds the covering number by a long product of covering numbers of polars, and successive applications of Lemma 10 collapse the product to two or three factors with absolute constants.

Why It Matters

The theorem verifies Pietsch's 1972 duality conjecture for entropy numbers of linear operators in the case where the domain or the range is a Hilbert space, equivalently when one of the two convex bodies is an ellipsoid. In learning-theory terms, a covering-number bound for a set in Euclidean metric transfers to a covering-number bound for the Euclidean ball in the dual norm, and back, at every scale. The authors note that both $N(K,tD)$ and $N(D,tK^\circ)$ enter the theory of Gaussian processes, citing Dudley among others.

Failure Mode

The general conjecture, with two arbitrary symmetric convex bodies $K$ and $T$ in place of $K$ and $D$, is not settled by this theorem. The constants are universal but not explicit, and the exponent is $2+\varepsilon$, not $1$. A companion paper of Artstein, Milman, Szarek and Tomczak-Jaegermann (GAFA, 2004) proves duality theorems when one of the bodies is K-convex, using a notion of convexified packing.

report a correction →

The paper closes with a statement about random projections, which is the part closest to Dvoretzky-type results. A random rank $t$ projection means a property holding on a set of orthogonal rank $t$ projections whose Haar measure tends to $1$ as the parameters grow.

Proposition

Covering Numbers of Random Projections (Artstein, Milman, Szarek, Proposition 16)

Statement

There are universal constants $c_1, C_1$, and for every $\lambda$ a constant $C_2(\lambda)$, such that for every $K \subset \mathbb{R}^n$ with $N(K, D) = 2^k$ and every integer $t_0$ with $k \le t_0 \le n$:

(i) If $M^*(K \cap D) \le \sqrt{t_0/n}$, then for every integer $t$ with $t_0 \le t \le n$ the random rank $t$ projection $P_t$ satisfies

$$N\!\left(P_t K,\ C_1\sqrt{t/n}\; D\right) \le 2^k \quad\text{and}\quad N\!\left(P_t K,\ c_1\sqrt{t/n}\; D\right) \ge 2^k .$$

(ii) Conversely, if the random rank $t_0$ projection satisfies $N(P_{t_0}K, \lambda\sqrt{t_0/n}\, D) \le 2^k$, then $M^*(K \cap D) \le C_2\sqrt{t_0/n}$, and for every $t_0 \le t \le n$ the two estimates in (i) hold with $C_2$ in place of $C_1$.

Intuition

A random rank $t$ projection shrinks a fixed unit vector by about $\sqrt{t/n}$, since the squared length of the projection has mean $t/n$. The proposition says that above a threshold $t_0$, set by the half mean width of $K \cap D$, the whole set $K$ shrinks by the same factor as far as covering numbers can see: the projection neither merges nor separates its $2^k$ pieces beyond constants.

Proof Sketch

The authors state that the proof follows the lines of their Lemma 3. They also note that, by the main theorem, the hypothesis on $N(K, D)$ can be replaced by one on $N(D, K^\circ)$, and that the projection estimates have dual analogues describing covering numbers of intersections of $K$ with random subspaces.

Why It Matters

This is the covering-number analog of a random projection guarantee. The Johnson-Lindenstrauss lemma controls a finite set by a union bound over pairs; here the complexity of $K$ is measured by $k = \log_2 N(K,D)$, and the threshold for the target dimension is governed by $M^*(K\cap D)$, the Gaussian-width parameter that also governs Dvoretzky's critical dimension.

Failure Mode

The conclusions hold for random projections with probability tending to one, not for every projection, and only above the threshold $t_0$. The constants $c_1, C_1, C_2$ are not explicit, so the statement fixes orders of magnitude, not numerical target dimensions.

report a correction →

Connections to Random Projections, JL and Learning Theory

Same template as JL. In the JL lemma the union bound runs over fewer than $N^2$ pairs of $N$ points, so the target dimension solves $N^2 e^{-ck\varepsilon^2} < 1$. In Milman's theorem the union bound runs over $(9/\varepsilon)^k$ net points, so the subspace dimension solves $(9/\varepsilon)^k e^{-c\varepsilon^2 n (M/b)^2} < 1$. Both reduce to one application of Gaussian or spherical concentration followed by counting.

Gaussian width. If the norm is a supremum of linear functionals, $\|x\| = \sup_{v \in T}\langle x, v\rangle$ for a bounded symmetric set $T$ spanning $\mathbb{R}^n$, then $\mathbb{E}\|g\| = \mathbb{E}\sup_{v \in T}\langle g, v\rangle$ is the Gaussian width of $T$ and $b = \max_{v \in T}\|v\|_2$. The critical dimension becomes

$$n\left(\frac{M}{b}\right)^2 = \frac{n}{(\mathbb{E}\|g\|_2)^2}\left(\frac{\mathbb{E}\sup_{v\in T}\langle g, v\rangle}{\max_{v\in T}\|v\|_2}\right)^2,$$

and the first factor lies between $1$ and $n/(n-1)$.

Complexity of function classes. For a sample $x_1, \ldots, x_m$ and a class $\mathcal{F}$, take $T = \{(f(x_1), \ldots, f(x_m)) : f \in \mathcal{F}\} \subset \mathbb{R}^m$. The expectation $\mathbb{E}\sup_{v \in T}\langle g, v\rangle$ is, up to the normalization convention, the empirical Gaussian complexity of $\mathcal{F}$, the Gaussian counterpart of Rademacher complexity. Chaining bounds on this quantity through covering numbers are the subject of empirical processes and chaining, and when the symmetric convex hull of $T$ has nonempty interior, the duality theorem above relates its Euclidean covering numbers to covering numbers of the Euclidean ball in the dual norm.

Where the log n limit bites. Coordinate-wise maxima behave like $\ell_\infty$ norms. The worked example shows that random subspaces see such a norm as Euclidean only up to dimension of order $\log n$, while $\ell_1$-type norms look Euclidean on random subspaces of dimension proportional to $n$. The restricted isometry property page studies a related question for sparse vectors and random matrices.

Common Confusions

Watch Out

Random subspaces of every dimension are not almost Euclidean

Milman's theorem stops at $n(M/b)^2$ and the upper bound shows the stop is real. For $\ell_\infty^n$ and a random $\sqrt{n}$-dimensional subspace $E$, the event $(1-\varepsilon)M < \|x\| < (1+\varepsilon)M$ on the unit sphere of $E$ has probability at most $1/2$ once $\sqrt{n} \ge C \cdot 2n\log(2n)/(n-1)$. In fact no subspace of that dimension is almost Euclidean for large $n$, by the $\log n$ bound for the cube.

Watch Out

The log n guarantee needs a change of position

The existential bound $k \ge c(\varepsilon)\log n$ holds for every norm. The random bound $c\,\varepsilon^2 n(M/b)^2$ depends on the coordinates, because $M/b$ changes under linear maps. The proof of Dvoretzky's theorem first moves the unit ball to the position where the Euclidean ball is the maximal volume ellipsoid, and only then takes a random subspace.

Watch Out

The epsilon squared rate is sharp for one version only

$\varepsilon^2$ is optimal for the random theorem stated in terms of $n(M/b)^2$ (Figiel's example) and in the maximal-volume-ellipsoid position (Tikhomirov's Proposition 2). It is not optimal for the existential theorem, where Schechtman (2006) reached $\varepsilon\log n/(\log(1/\varepsilon))^2$. Quote the version when quoting the rate.

Watch Out

Artstein-Milman-Szarek is an entropy duality theorem

Their 2004 Annals paper proves that $N(K, tD)$ and $N(D, tK^\circ)$ are equivalent up to universal constants. It uses the half mean width of sections and random projections, which are Dvoretzky-Milman tools, but it does not improve the dimension or the $\varepsilon$ dependence in Dvoretzky's theorem.

Summary

• Dvoretzky: every $n$-dimensional normed space has a $(1+\varepsilon)$-Euclidean subspace of dimension at least $c(\varepsilon)\log n$, and $\log n$ is sharp for $\ell_\infty^n$.
• Milman: random subspaces of dimension up to $c\,\varepsilon^2 n(M/b)^2/\log(9/\varepsilon)$ are almost Euclidean, via spherical concentration, a $(9/\varepsilon)^k$ net and a union bound. Gordon and Schechtman removed the logarithmic factor.
• Huang-Wei: for a universal $C$ and every norm, a random subspace of dimension larger than $C n(M/b)^2$ satisfies the two-sided estimate around $M$ with probability at most $1/2$, so $n(M/b)^2$ is the critical dimension. Milman-Schechtman had an upper bound of the same order with the threshold $n/(n+k)$, under the condition $M/b > c\sqrt{\log n / n}$.
• $\ell_1^n$ has critical dimension of order $n$, $\ell_\infty^n$ of order $\log n$.
• The existential $\varepsilon$ dependence is better than the random $\varepsilon^2$: Schechtman (2006) proved $\varepsilon\log n/(\log(1/\varepsilon))^2$.
• Artstein-Milman-Szarek proved duality of metric entropy, $N(K,tD)$ versus $N(D,tK^\circ)$, and a covering-number statement for random projections at scale $\sqrt{t/n}$.

Exercises

ExerciseCore

Problem

Compute $b$ and bound $M$ for $\ell_1^n$, and show $n(M/b)^2 \ge 2n/\pi$. Use $\mathbb{E}|g_1| = \sqrt{2/\pi}$ for a standard Gaussian.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $E_0$ be a $k$-dimensional subspace, $\mathcal{N}$ a $\delta$-net of its unit sphere with $\delta \le 1/4$, and $U$ a linear map with $(1-\delta)M \le \|U\theta\| \le (1+\delta)M$ for every $\theta \in \mathcal{N}$. Show that $(1 - \tfrac{8}{3}\delta)M \le \|Ux\| \le (1 + \tfrac{8}{3}\delta)M$ for every unit $x \in E_0$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that every norm on $\mathbb{R}^n$ has $k(X) = n(M/b)^2 \ge 2/\pi$. Then compute $n(M/b)^2$ for $\|x\| = \max(\|x\|_2, \sqrt{n}|x_1|)$ up to constants, and name a subspace of dimension $n-1$ on which this norm is exactly Euclidean.

Hint

Reveal Solution

ExerciseResearch

Problem

For a symmetric convex body $K$ with $N(K, D) = 2^k$, compare the threshold $M^*(K \cap D) \le \sqrt{t_0/n}$ in Proposition 16 of Artstein, Milman and Szarek with the critical dimension of the norm $\|\cdot\|_{(K \cap D)^\circ}$. Express the smallest $t_0$ allowed in part (i) in terms of $k$ and that critical dimension, and state what the paper's Geometric Lemma conjecture would give for convex hulls of $2^k$ points.

Hint

Reveal Solution

References

Canonical:

• Dvoretzky, A. (1961). "Some results on convex bodies and Banach spaces." Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pp. 123-160. The original theorem.
• Milman, V. D. (1971). "A new proof of A. Dvoretzky's theorem on cross-sections of convex bodies." Funkcional. Anal. i Prilozhen. 5(4), pp. 28-37; English translation: "New proof of the theorem of A. Dvoretzky on sections of convex bodies," Funct. Anal. Appl. 5(4), pp. 288-295. Concentration proof and the log n dimension.
• Gordon, Y. (1985). "Some inequalities for Gaussian processes and applications." Israel J. Math. 50(4), pp. 265-289. doi:10.1007/BF02759761. First proof of the epsilon squared dependence.
• Schechtman, G. (1989). "A remark concerning the dependence on epsilon in Dvoretzky's theorem." Geometric Aspects of Functional Analysis (1987-88), Lecture Notes in Math. 1376, pp. 274-277. doi:10.1007/BFb0090061.
• Milman, V. D., and Schechtman, G. (1997). "Global versus local asymptotic theories of finite-dimensional normed spaces." Duke Math. J. 90(1), pp. 73-93. doi:10.1215/S0012-7094-97-09003-7. Upper bound on the Dvoretzky dimension.
• Artstein, S., Milman, V. D., and Szarek, S. J. (2004). "Duality of metric entropy." Annals of Math. 159(3), pp. 1313-1328. doi:10.4007/annals.2004.159.1313. arXiv:math/0407236. Theorem 1 and Proposition 16.

Current:

• Schechtman, G. (2006). "Two observations regarding embedding subsets of Euclidean spaces in normed spaces." Adv. Math. 200(1), pp. 125-135. doi:10.1016/j.aim.2004.11.003. Existential dependence epsilon log n over log squared.
• Schechtman, G. "Euclidean sections of convex bodies." Lecture notes from Bedlewo and Kent, 2008. arXiv:1110.6401. Theorems 1.2 and 1.5, Proposition 3.1, Claims 3.2 to 3.4, Theorem 4.1.
• Artstein-Avidan, S., Giannopoulos, A., and Milman, V. D. (2015). Asymptotic Geometric Analysis, Part I. Mathematical Surveys and Monographs 202, AMS. Chapter "Almost Euclidean subspaces of finite dimensional normed spaces."
• Vershynin, R. (2018). High-Dimensional Probability. Cambridge University Press. Chapter 11, "Dvoretzky-Milman theorem," pp. 254-264.
• Huang, H., and Wei, F. (2017). "Upper bound for the Dvoretzky dimension in Milman-Schechtman theorem." Geometric Aspects of Functional Analysis, Lecture Notes in Math., Springer, pp. 181-186. doi:10.1007/978-3-319-45282-1_12. arXiv:1612.03572. Theorems A and B, Remark (2).
• Artstein, S., Milman, V. D., Szarek, S. J., and Tomczak-Jaegermann, N. (2004). "On convexified packing and entropy duality." Geom. Funct. Anal. 14(5), pp. 1134-1141. doi:10.1007/s00039-004-0486-3. arXiv:math/0407238.

Frontier:

• Tikhomirov, K. (2018). "Superconcentration, and randomized Dvoretzky's theorem for spaces with 1-unconditional bases." J. Funct. Anal. 274(1), pp. 121-151. doi:10.1016/j.jfa.2017.08.021. arXiv:1702.00859. Theorems 1 and 3, Proposition 2.
• Artstein-Avidan, S., and Milman, V. D. (2006). "Logarithmic reduction of the level of randomness in some probabilistic geometric constructions." J. Funct. Anal. 235(1), pp. 297-329. doi:10.1016/j.jfa.2005.11.003. As summarized by Lovett and Sodin (arXiv:math/0701102), it runs the random constructions behind results from Milman's quotient of subspace theorem to zig-zag approximation on a small number of random signs, and uses $O(N\log N)$ random bits for proportional almost Euclidean subspaces of $\ell_1^N$.

Next Topics

• Dimensionality reduction theory: random projections as an algorithmic primitive, with the JL guarantee that shares Milman's proof template.
• Empirical processes and chaining: bounds on expected suprema of Gaussian processes, the Gaussian width in Milman's formula.
• Restricted isometry property: near-isometry of random matrices on sparse vectors.
• Random matrix theory overview: spectra and deviations of random matrices.