The Wayback Machine - https://web.archive.org/web/20200927015405/https://blogs.princeton.edu/imabandit/2013/06/22/icml-and-isotropic-position-of-a-convex-body/

ICML and isotropic position of a convex body

Posted on June 22, 2013 by Sebastien Bubeck

ICML 2013 just finished a few days ago. The presentation that inspired me the most was the invited talk by Santosh Vempala. He talked about the relations between sampling, optimization, integration, learning, and rounding. I strongly recommend Vempala’s short survey on these topics, it is an excellent read. I also would like to point out two papers by Vempala on optimization that are very interesting and exceptionally well written: the first paper (with Bertsimas) presents an optimal (in terms of oracle complexity) algorithm for convex optimization with a much better computational complexity than the Center of Gravity method (but still slightly worse computational complexity than the Ellipsoid Method); the second paper (with Kalai) gives a more efficient algorithm than the Ellipsoid Method for linear optimization with a membership oracle (instead of a separation oracle).

Vempala’s talk gave me the motivation to write on a related topic which has many applications in optimization, probability and statistics: this is the notion of an isotropic convex body. A convex body K \subset \mathbb{R}^n is centered and isotropic if it satisfies:

    \[\int_{K} x \ dx = 0, \;\; \frac{1}{\mathrm{vol}(K)}\int_{K} x x^{\top} \ dx = I_n .\]

First observe that the hypercube [-c,c]^n is isotropic (with c of order 1/2), and it is a one line calculation to show that c \sqrt{n} B_n (with B_n being the Euclidean ball of unit radius and c some numerical constant) is also isotropic. It is also immediate that any convex body can be put in isotropic position up to an affine transformation. Interestingly it was shown in this paper that one can find an approximate isotropic transformation with a linear (in n) number of samples from the uniform distribution on K.

 

If you read papers about isotropic convex set they often use a definition where \mathrm{vol}(K) = 1, in which case the second moment condition writes

    \[\int_{K} x x^{\top} \ dx = L_K \ I_n .\]

The term L_K is called the isotropic constant. However this definition of isotropy is not easy to work with because there is a deep conjecture related to the order of magnitude of the isotropic constant. It is easy to see that L_K has to be at least some numerical constant, but the statement that L_K is also upper bounded by a numerical constant is equivalent to the Hyperplane Conjecture (which I describe below). For this reason we stick to the definition with the second moment normalization.

 

The question we want to explore now is the following: ‘what looks like an isotropic convex body K‘? We are especially interested in the answer for the high-dimensional regime where n is very large. The following three results give interesting and useful results in that direction. I use c to denote some numerical constant.

KLS lemma

    \[\sqrt{\frac{n+2}{n}} B_n \subset K \subset \sqrt{n (n+2)} B_n .\]

It can be shown that the above inequalities are both tight in the simplex case.

We describe the next results in terms of a random variable X uniformly distributed on K. Since K is isotropic one has \mathbb{E} \|X\|_2^2 = n. The next result shows that in fact X has norm of order \sqrt{n} with high probability.

Theorem (Paouris’ inequality)

For any t \geq 1,

    \[\mathbb{P}(\|X\|_2 \geq c t \sqrt{n} ) \leq \exp(- t \sqrt{n}) .\]

The next statement is still a conjecture, it concerns a much more refined concentration inequality for the norm of an isotropic random variable.

Thin Shell Conjecture

For any t > 0,

    \[\mathbb{P}\bigg(\big|\|X\|_2 - \sqrt{n}\big| \geq t \bigg) \leq \exp(- c t) .\]

Since we are now talking about conjectures I cannot resist giving you the most important conjecture in convex geometry:

Hyperplane Conjecture

For any centered isotropic K there exists an hyperplane H such that

    \[\mathrm{vol}(K \cap H) \geq c \ \mathrm{vol}(K) .\]

As of today the best result we know replaces c by n^{-1/4} in the above inequality (this is a theorem of Bourgain up to a log factor, and the log factor was removed by Klartag). To the unexperienced eye as mine it seems unbelievable that this is still a conjecture: it looks clearly true! The following theorem reminds us that the set of statements that look true is not equal to the set of true statements…

Theorem (Busemann-Petty problem)

If n> 4 there exists centered convex sets K_1 and K_2 such that for all hyperplanes H one has

    \[\mathrm{vol}(K_1 \cap H) \leq \mathrm{vol}(K_2 \cap H) ,\]

and

    \[\mathrm{vol}(K_1) > \mathrm{vol}(K_2) .\]

This entry was posted in Uncategorized. Bookmark the permalink.

5 Responses to "ICML and isotropic position of a convex body"

  • By Gilles BONNET March 30, 2014 - 5:29 pm

    I found your nice post while searching info about the hyperplane conjecture. “To the unexperienced eye as mine it seems unbelievable that this is still a conjecture: it looks clearly true!” ahah! I want to say exactly the same. And that is why I posted the following question: http://math.stackexchange.com/questions/724786/about-the-hyperplane-conjecture
    Do you know if there exist any example of convex body with a maximal hyperplane section smaller then the one of the sphere?

    Reply
  • By Hein Hundal June 28, 2013 - 8:54 am

    I’m trying to make sure I understand the definition of an isotropic convex body. For the hypercube [-1,1]^n, when I integrate x x^T, I get 2/3*I. So, I would think that
    [-sqrt(3/2), sqrt(3/2)]^n would be an isotropic convex body. Am I correct?

    Reply
    • Sebastien Bubeck
      By Sebastien Bubeck July 1, 2013 - 8:11 am

      You’re absolutely right, thx for spotting the typo! I forgot the normalization by 1/vol(K) so this changes a bit the calculation and the constants are in fact dependent on n now… I leave them unspecified in the post.

    • By Hein Hundal July 1, 2013 - 10:28 am

      Let’s say that K, a closed convex subset of R^n is a type 1 isotropic convex body (ICB1) if

      1) K contains the origin,
      2) the integral over K of x is the zero vector,
      3) the integral over K of x x^T is the identity matrix times the volume of K.

      I think [-c,c]^n is ICB1 if c = sqrt(3).

      I wonder if the “thickest shell” might occur if K is a regular simplex.

      I would think that the distribution of the norm of x squared for random variable uniformly distributed over any ICB1 set would be approximately chi squared with n degrees of freedom, but it would have finite support because of the KLS lemma. I looks like the expected value of the norm squared would be the trace of the identity = n.

Leave a reply