Theory Seminar: A Generalized Central Limit Conjecture, Haotian Jiang (UW)

Theory Seminar: A Generalized Central Limit Conjecture, Haotian Jiang (UW)

Articles Blog


Yeah, thank you. So the topic of this talk is
a generalized central limit conjecture for convex bodies. And this is joint work
with Yin Tat and Santosh. So let’s start with the
central limit theorem that we all learned
in probability. And so this is the textbook
version of central limit theorem that I
learned, that suppose we were given n IID
samples, X1 to Xn, from some good enough
distribution with 0 mean. Then the sum of these
random variables, Xi, scaled by a factor of
1 over square root of n, this thing converges
in distribution to a Gaussian distribution. So in the theorem I learned
from probability course, this “good” means that you
have some bounded, say, second moment. So another way to
interpret this result is suppose we write this X1
to Xn as n-dimensional vector. Then this vector has a
product distribution. And so equivalently, the
textbook central limit theorem can be stated as
the inner product of this n-dimensional
vector, X1 to Xn, with a unit vector
where each coordinate is 1 over square root of n. This inner product is
close to a Gaussian. So natural question to
ask is, what if we have other distributions other than
probability as our product distribution, and
what if we look at the marginal distribution
of this distribution in other directions? And this is the motivation
for the central limit theorem for convex bodies. And before we can talk
about the central limit theorem for convex
bodies, we need to first introduce
some notion called isotropic log-concave measures. So a density function p
is called log-concave. It takes the form exponential
of a negative convex function f. And a probability measure
is called log-concave if it has a log-concave density. The typical examples
of log-concave measures include the uniform
measure on convex bodies and the Gaussian measure. So let’s see why these
measures are log-concave. So I guess for the Gaussian
measure, it’s straightforward. But for the uniform
measure on the convex body, we have the density
inside the convex body is 1 over the volume
of the convex body. And the density outside is 0. So that function f would take a
constant inside the convex body and infinity outside. So it’s crucial that
we allow the function f to take value infinity. And at the point where
it takes value infinity, it just means the density
at that point is 0. So now a probability
measure is called isotropic if it has 0 mean and
identity covariance. And the canonical example
of an isotropic log-concave distribution is the
standard Gaussian measure in Rn, which I will
write as N 0, identity. So now we are given
these definitions, we are ready to state
the central limit theorem for convex bodies. And roughly, it is as follows. So the central limit theorem
for convex bodies states that suppose we are given an
isotropic log-concave measure p in Rn, and we sample
random vector y from p. Then we have this guarantee,
which is a little bit hard to explain. So roughly, it says
that along most of the directions
on the unit sphere, the marginal distribution of the
isotropic log-concave measure on that direction is
close to a Gaussian. So more concretely, let’s try
to look at this long formula. So this probability is
taken only with respect to the vector x which is sampled
randomly on the unit sphere. And this total variation
distance is only with respect to the randomness of
the vector y, which is from the isotropic
log-concave distribution. So what this is
saying is that most of the direction,
all but cn fraction of the direction
on the unit sphere, if we project the isotropic
log-concave measure p until the direction x,
then we have something that’s close to the standard
normal distribution where this notion of close is
saying that its total variation distance is bounded
by some cn where cn is the sequence of
constants that goes to 0 as n goes to infinity. So there is the– yeah? AUDIENCE: So this doesn’t
mention convex body just because log-concave measure, so
it’s really stronger than that. Is that the– HAOTIAN JIANG: Yeah. I guess originally,
this thing is saying that if you have
a uniform distribution over isotropic convex bodies,
then you have this guarantee. But it turns out
it can generalize to any isotropic
log-concave distributions. So yeah, any other
questions, or are we all happy with this
mysterious definition? AUDIENCE: Is this
equivalent, by the way, to say that [INAUDIBLE]
log-concave distribution that are convex bodies? HAOTIAN JIANG: OK, at
that, I’m not sure. I always think intuitively
that it’s equivalent, but I don’t know a
formal statement of that. So there’s a long
line of work that– yeah? AUDIENCE: The probability’s
over x and y, right? HAOTIAN JIANG: So this
probability, it’s only over x. So you uniformly sample a
direction on the unit sphere and then fix this direction. You look at the projection
of your isotropic log-concave measure onto this
direction and ask, is this distribution close
to the standard normal distribution? Yeah, so there’s a long
line of work that– AUDIENCE: [INAUDIBLE]
doesn’t make sense, right? I guess it’s a– AUDIENCE: You’re looking at
a distribution of a line. AUDIENCE: Yes. HAOTIAN JIANG: Yeah, [INAUDIBLE]
one-dimensional margin of my isotropic
log-concave distribution. AUDIENCE: [INAUDIBLE]
y is a random variable. HAOTIAN JIANG: Oh, no. I guess that only comes in
this total variation distance. AUDIENCE: So this
inner product, x and y, is really this distribution
projection, which is just– HAOTIAN JIANG: Yeah, exactly. AUDIENCE: That’s the
part that’s confusing. HAOTIAN JIANG: Yeah,
just, I’m writing it this way [INAUDIBLE]. AUDIENCE: It’s really
p projected on x. HAOTIAN JIANG: Yeah, exactly. Exactly, yeah. So yeah, maybe that’s a
better way of writing it. So right. So there’s the list of
work that gets the improved bounds on [INAUDIBLE]
constant cn or how fast this converges to 0. The first one of
these is by Klartag, which proves that this
constant cn is bounded by 1 over square root of log n. And this is the work that
makes this central limit theorem for convex bodies. And I guess in the
same year, there is also a weaker bound,
like cn less than or equal to 1 over
log n to the 1 over 6. And later on, this is
improved by Klartag to 1 over some poly n and
a few follow-up work. So this leads to current
best bound on cn, which is 1 over n
to the one quarter. This is by Lee and
Vempala in 2017. So in these bounds, there
might be some log factors that I’m hiding. So how do we derive
these bounds? [INAUDIBLE] that
all these bounds are derived by a
notion of thin shell. So the motivation for thin
shell is the following. Suppose I randomly
sample a vector x from an isotropic
log-concave distribution. Then the expectation
of the Euclidean norm square of x is n. So throughout this talk, I will
use this magnitude notation to denote the Euclidean norm. It just looks simpler. So if I sample random
isotropic log-concave vector, then the expectation of
its Euclidean norm square is going to be n. And moreover, there’s
this concentration of the Euclidean norm of
x around square root of n. And the thin-shell
constant captures how much it concentrates
around square root of n. So the thin-shell constant
is defined as sigma n is the thin [INAUDIBLE]. Sigma n squared is defined
to be the expectation of the x minus square root
of n squared expectation. And moreover, you take the sup
over all isotropic log-concave measures in Rn. So roughly, this quantity
on the right-hand side is close to the variance
of the Euclidean norm of x. They’re close up to
a constant factor. But this whole thing–
so in some literature, you see this as the
definition of sigma n squared. They are equivalent up
to a constant factor. But the important thing
is that all these things are much smaller
than the expectation of the Euclidean norm of x,
which is square root of n. So that’s why I say
it concentrate around square root of n. And the first result that
proves this concentration is by Klartag, which
shows that sigma n, the thin-shell constant,
is bounded by square root of n over square root of log n. And the current best result
on the thin-shell constant is by Lee and
Vempala, which proves that sigma n is less than or
equal to n to the one quarter. So yeah, the famous
thin-shell conjecture by Anttilla-Ball-Parissinaki
and Bobkov-Koldobsky states that there should be
a universal constant such that the thin-shell constant
is bounded by C for all n. So what is the– I mentioned earlier that all
these results on central limit theorem is via the
thin-shell constant. So what is the connection
between the central limit theorem and thin shell? Let’s recall the
central limit theorem. And suppose you give me an
isotropic log-concave measure in Rn. Then along most of the
directions on the unit sphere, the marginal distribution of
this isotropic log-concave measure onto that unit direction
x is close to a Gaussian where the quantitative
convergence is cn. And it turns out that,
by a theorem of Bobkov, the connection is
that the cn is bounded by the thin-shell constant
divided by square root of n. And if we go back to
the previous slides, this would suggest that
this bound by Klartag gives us a bound on cn
less than or equal to 1 over square root of log n,
which is what I showed earlier. So it turns out that the
thin-shell and central limit theorem are all related to this
notion called isoperimetry. The isoperimetry
question asks, what’s the least surface area of a
set with a certain volume? And so it turns out, for
the Lebesgue measure in Rn, we know that the
answer is the ball. And how about the
probability measures? So to answer this
question, we first need to define surface area
for a probability measure. So suppose we are given
a probability measure p. We define the
surface area, which is p plus A. We
define the surface area as how fast
the measure of A expand when I include
all the points that’s close to its boundary. So this notion, A epsilon,
is defined as all the points that is epsilon close, in
Euclidean norm, to the set A. And the surface area or
boundary measure of A is defined as the lim inf of– you include epsilon-close
points and how much the measure increases. What’s the rate of the
increase of the volume when you increase epsilon? And the KLS constant for
measure p is defined as follows. So KLS constant is this psi p. So the reciprocal
of that is defined as the lowest expansion–
sorry, lowest expansion of all the sets with
measure at most 1/2. And it turns out,
by log concavity– so if p’s an isotropic
log-concave measure, then this inf is taken for a
set with measure exactly 1/2. So up to a constant
factor, we can write it just as the infimum of the
surface area or boundary measure over all sets
with measure 1/2. And the KLS constant
for psi n is defined as the
supremum for psi p over all isotropic
log-concave measure p in Rn. AUDIENCE: [INAUDIBLE] HAOTIAN JIANG: It’s
not that easy to see, but it’s just using the
definition of log concavity. And you can do some
calculation to get that. Yeah, but I agree. It’s not that straightforward. AUDIENCE: Probably not
essential either, right? I mean, you will not try
to prove the KLS conjecture by using exactly 1/2. So it’s not– HAOTIAN JIANG: I think
the Lee-Vempala paper uses this fact, that you look
at the measure 1/2 set and show that it’s
not going [INAUDIBLE].. AUDIENCE: [INAUDIBLE] so yeah. [LAUGHTER] So then– no, but is
that symmetry essential? Like, if [INAUDIBLE] HAOTIAN JIANG: Yeah,
it’s not too essential. AUDIENCE: OK. HAOTIAN JIANG: OK. Yeah, so the KLS conjecture
basically states that if p is an isotropic log-concave
distribution– oh, sorry. So first, let’s talk
about all the sets formed by hyperplane cut. So it turns out, if p is
isotropic log-concave measure and H is a hyperplane,
then we have the surface area of H is constant. So therefore, the KLS constant
for all the hyperplane cut is constant. And the KLS conjecture, by
Kannan, Lovász, and Simonovits, states that there exists a
universal constant such that the KLS is bounded by
a constant for all n. So this, together
with our observation that the KLS constant
for hyperplane is constant, basically states
that up to a constant factor, the worst isoperimetric
sets are half-spaces. AUDIENCE: Is there
a good intuition as to why the answer is– the y is lower-bounded by
a constant for hyperplanes? HAOTIAN JIANG: I
always imagine if you look at Gaussian measure. If you look at Gaussian
measure, then you look at the hyperplane that
cuts a Gaussian measure that is a constant. And it turns out, then, I
think, in Gaussian measure, even the worst– without this constant factor,
the worst isoperimetric sets are half-spaces. But this is stating a
generalization of that, saying that for general
isotropic log-concave measures, then you are worse up
to a constant factor by a hyperplane cut. AUDIENCE: So these are
hyperplanes through the origin? HAOTIAN JIANG: Uh– AUDIENCE: For the
original– yeah. HAOTIAN JIANG: Yeah, because
we restrict our attention, say, only on the set
with measure half. Then for– oh, you mean for a
general isotropic log-concave measure, it’s not
necessary, yeah. But for a Gaussian, I’m saying
then it’s through the origin. So I’ve talked about KLS and
thin shell and central limit theorem. Let’s try to summarize
the connections between these notions. So we have a centralized limit
theorem, thin shell, KLS. Recall the definition. Central limit theorem
basically says the margin of p, on most of direction,
is close to Gaussian. And thin shell basically
states that the variance of– thin shell, the
definition of that is the variance of the
Euclidean norm of x. And KLS is the
measure of s divided by the boundary measure of s. And so the conjectured bound
for these three quantities is 1 over square root of n. AUDIENCE: [INAUDIBLE] HAOTIAN JIANG: Oh, I
defined 1 over psi p as the boundary measure
divided by the measure. I guess this is– AUDIENCE: [INAUDIBLE] at least? It is at most a constant? HAOTIAN JIANG: So the reciprocal
of this– so the boundary measure divided by the measure,
this is at least something. So if you flipped
that, then it’s going to be at most something. So I guess this is
just for convenience. So any other questions so far? AUDIENCE: [INAUDIBLE]
boundary is very small. If the boundary is– AUDIENCE: Any way of
splitting the measure in half as a large expansion? [INAUDIBLE] expansion is large. AUDIENCE: [INAUDIBLE] HAOTIAN JIANG: So
I guess maybe– AUDIENCE: The universe is small. [INAUDIBLE] AUDIENCE: [INAUDIBLE] is small. This is– HAOTIAN JIANG: Yeah, so my
definition is 1 over psi p is this thing. So take the reciprocal. You get the psi p
upper-bounded by something. Yeah, so these are all
the conjecture bounds. So what’s the connection
between all these quantities? So it turns out that the
KLS constant, the psi n, upper-bounds the thin-shell
constant, sigma n. And this is by inequality
of Cheeger, which I’m not going to talk in detail. And the reverse direction
was recently proved by Eldan, stating that the thin-shell
constant implies the KLS constant up to a log factor. And so as mentioned earlier,
the thin-shell constant will give some bound on
the central limit theorem. And this is by Bobkov. And it turns out the
reverse direction is also fine by some calculations. So all these are
classical results. AUDIENCE: Which ones
are [INAUDIBLE]?? What about the two on the left? HAOTIAN JIANG: So basically,
if thin shell is constant, then his result
implies KLS is log n. AUDIENCE: Yeah, I know. But the one on the left, is
there a loss on the left, or is it– HAOTIAN JIANG: So you
mean this one there? I think this one, there is
a log n factor loss, yeah. Yeah, but because the
current bound of these are all polynomials,
so that log factor is not crucial at the moment. AUDIENCE: [INAUDIBLE]
also related to the isoperimetry
conjecture, that you have a convex set of volume
1, it’s isotropic, [INAUDIBLE] through the origin, [INAUDIBLE]? HAOTIAN JIANG: It’s just
called the slicing conjecture. AUDIENCE: Oh, I think
that’s slicing conjecture. HAOTIAN JIANG: Yeah,
I think that constant is bounded by KLS constant. So the reverse direction,
I don’t think it’s no. AUDIENCE: [INAUDIBLE]
it’s just the– I mean, what you said is just
about whether the expansion can be 0, basically. Like, it’s– OK, what
you said was just– like, isn’t the slicing
problem just about the– well, I guess I don’t know. OK. Yeah, we maybe can
chat offline for that if there’s some interest. OK, so yeah, this
is all known before. And now, to motivate this notion
of generalized central limit theorem, let’s come
back to central limit theorem for convex bodies. So it basically states this. As I mentioned many times,
it’s like, the marginal of this isotropic
log-concave measure on most of the directions is
close to a Gaussian. And so if we think of
this uniform distribution on the sphere as being close
to the standard Gaussian, because there is those standard
concentration of Gaussian measure, then we can restate
this central limit theorem for convex bodies as saying
that the inner product of an isotropic log-concave
vector with a standard Gaussian vector, this is close
to a Gaussian for most of the Gaussian direction. And so a natural question to
ask is, how about you take– I give you two isotropic
log-concave measures. And you sample random
vector from each one and take the inner product. Is this also close
to a Gaussian? Basically, can we generalize
this Gaussian vector here to any isotropic
log-concave measure? Yeah, and we formulate
this question as the generalized
central limit theorem. And so this
definition of this is saying that suppose
we are given two isotropic log-concave
measures in Rn. Sample x, y independently
from p and q and a Gaussian random
variable, G. So notice here, I put variance is n. It’s not a standard
Gaussian random variable. And then we define
this, the W2 distance between the inner
product of x and y and G. Let’s call
this kappa p, q. So recall the
Wasserstein distance here between two measures, mu and nu. It’s basically the infimum
over all coupling of the ls norm under this coupling. And again, we
define this kappa n to be the largest kappa p, q
over all isotropic log-concave measures in Rn. And in the later
part of this talk, I will call this kappa n as
the generalized central limit constant. Yeah? AUDIENCE: So how
should we think of pi? HAOTIAN JIANG: How should
we think of pi in which one? AUDIENCE: So you’ve got– so in your definition. So by the coupling,
you’re mapping the space? I just– yeah. HAOTIAN JIANG: So– AUDIENCE: [INAUDIBLE]
mu to nu, and you want to minimize the
total [INAUDIBLE] distance that the particles move. HAOTIAN JIANG: So we
put them on the same– AUDIENCE: So this is– AUDIENCE: [INAUDIBLE] AUDIENCE: So this
is [INAUDIBLE] type? HAOTIAN JIANG: Yeah,
[INAUDIBLE],, yeah. So I guess the formal
definition of this is you create the product
distribution– sorry, not the product. You create a distribution on
the product space of mu and nu. And so that it’s
marginal, it’s mu and nu on the corresponding space
and over all such kind of distribution, yeah. AUDIENCE: I mean,
the generalized CLT does not imply the CLT, is
weaker because you used W2. HAOTIAN JIANG:
Yeah, yeah, yeah,. So the classical [INAUDIBLE] for
a kind of [INAUDIBLE] can be, think of it as like a high
dimension– sorry, high probably estimate. Like over most directions,
it’s something. This is, I’m saying that
I’m joining vectors, and then look at the distance,
without any like high probability statement. Yeah so, right,
so the naive bond on the generalized
central limit conjecture is that this kappa n is
bounded by square root of n, and this follows
from the observation that the expectation of the
inner product square, this is n. And also, the expectation of the
Gaussian random variable is n. Because the variance is n. And you just take the
square root on both sides, and you get that naive bound
kappa n is square root of n So the conjecture we made about
the generalized centroid limit is that there exists a
universal constant such that kappa n is bounded by
that constant for all n. So what is the
connection between the generalized central
limit conjecture and the KLS conjecture? And so the main theorem we
proved in the paper is that, basically, the central
limit, generalized central limit
constant is roughly the KLS constant squared. So this, roughly,
this approximation is hiding, like, log factors. But since the
current bound of KLS constant is still
polynomial, so I would just ignore that in this talk. So at the current
best bound on the KLS constant is beside and
bounded by n to the 1/4. And this gives,
using the theorem, that kappa n is founded
by square root of n, which is the naive bound on
generalized central limit theorem. So this result doesn’t– using the current
on KLS conjecture, doesn’t really give
some, like, a non-trivial bound on the generalized
central limit theorem. But if the KLS conjecture
is true, [INAUDIBLE] bonded by constant,
then we have a kappa n is bounded by constant, and so
the generalized central limit conjecture is also true. So kind of this theorem is
kind of a conceptual thing, saying that any quantitative
improvement each one of these conjectures leads
to similar improvements in each other. OK so, in the rest
of the talk, I will describe how to
prove this connection. And so our proof
of the connection between generalized centroid
limit conjecture and KLS conjecture is
through this notion called third moment bound. And so the third
moment is defined as, like, if I’m given p q,
two isotopic log concave measures, p q, and r n,
then the third moment is defined as the expectation
of the third movement of their inner product. It turns out the
Lee-Vempala bound of psi n bounded by 1 to
the 1/4 on KLS constant is essentially saying
the third moment is bounded by n to the 1.5. And we’ll build our
equivalence between generalized central
conjecture and KLS conjecture through this third moment bound. So roughly our picture
proof is the following. So we show that generalized
central limit theorem implies the third moment, and then show
that the third moment implies KLS, and then the KLS implies
the generalized central limit theorem. And moreover, we proved this
quantitative implication that, if the generalized central
limit constant is n to the 0.5 minus epsilon, then the
corresponding third moment bound is going to be n
to the 1.5 minus epsilon. And the KLS bound is going
to be n to the 1/4 minus 1/2 of epsilon. So we start by showing that
generalized central limit constant being bounded
by this, implies the third moment being bounded
by n to the 1.5 minus epsilon. So formally speaking, the
theorem we prove is this. So suppose we fix epsilon,
which is between 0 and 1/2, and let p be an isotropic
log-concave measuring our n. And we draw independent
random vectors x, y from p, and Gaussian random variable. Also notice here,
I only have one– we only have the same
isotropic log concave measure. So recall, in generalize
central limit theorem, we have two isotropic
log concave random– two isotopic log-concave
distributions, p and q, and we draw vectors from each one. But here, it turns
out that you just give me one isotropic
log-concave measure, and tell me this, then
it’s enough to prove the bound on the third moment. So if the W-2 distance
between x, y, and G, that this is bounded by
into the 0.5 minus epsilon, then we have the third
moment being bounded by n to the 1.5 minus epsilon. Any question about
the statement of this? OK. So now let’s try to prove this. And so basically the previous
just by the definition of these notions. So let’s call pi 2 the best
coupling in this W2 distance. And then it follows
by definition that, under the coupling
pi 2, the expectation is n to the 1 minus 2 epsilon. This is just definition. So it turns out, that
by the monotone property of Watt’s sustained
distance, we can show something about
the third moment under this coupling, pi 2. So the third moment
is founded by n to the 1.5 minus 2
epsilon [INAUDIBLE].. The way to understand this
is to do some normalization. So basically, this
g has various n. So let’s try to divide
both sides by n. And then this will become big O
of n to the negative 2 epsilon. And then do the same
normalization here. This will become big O of n
the negative 2 epsilon log n. So kind of the
Monotone property is saying that, after
normalization, then this is bounded by this
up to a log n factor. AUDIENCE: [INAUDIBLE] HAOTIAN JIANG: Which one? AUDIENCE: [INAUDIBLE]
What was the proof? HAOTIAN JIANG: I
didn’t give a proof. I’m saying the way to
kind of understand this. So because the tricky
part is this 1.5. This is 2 epsilon. This is 2 epsilon. This is 1. This is 1.5. But I’m just claiming that,
after normalization, this 1.5 will be gone. This 1 will be gone. And kind of the statement is
that, after the normalization, third moment is bounded
by the second moment times some poly log factor. AUDIENCE: I guess that
the way you’re using it. I mean, in general,
you’re not going to bound a third moment
by a second moment? That’s not right. But here, you’re using the fact
that there is some kind of– HAOTIAN JIANG: Yeah,
I’m using the fact that you are like having x,
y both isotropic log-concave. AUDIENCE: So you’re
using tails of some sort. HAOTIAN JIANG: Yes. This is exactly a tail bound. AUDIENCE: The second
moment, and you can try to apply to
the third moment, you won’t get
something interesting. HAOTIAN JIANG: That’s true. That’s more generalized. AUDIENCE: Then you will. HAOTIAN JIANG: Yeah, so
essentially the proof is, like, you use the
tail bound and say that x, y are, like, at most,
some constant times square root of n. Yeah, this is not
true in general. OK, so. OK yeah, so using this
and the coupling pi 2, we can write the third
moment bound as– so we put a negative
g and a plus g inside and then
expand this equation. So the first term,
expectation with G Q, this is 0 because G is symmetric. And the last term, x1 is GE
cubed using the bound above. This is bounded by n to
the 1.5 minus epsilon. So we’re also good about that. So the remaining two terms
that we need to bound is the second and
the third terms. And so basically, these are
just like using Cauchy Schwarz inequality. So for the second term,
we separate this G squared and the x, y minus G as
using Cauchy Schwarz. And so the first term, the
fourth moment of the Gaussian variables, the square root of
that, that is bounded by order n. The second term, so that is
bounded by the definition of the W2 distance. This bounded by n to
the 0.5 minus epsilon. So this term, we are done. For the other term, we
also use Cauchy Schwarz, but with some different p and q. And we can show this
is, again, bounded by n to the 1.5 minus epsilon. So I’m not going to go through
the calculation carefully. OK. So therefore, we
conclude that we have– the third moment is bounded
by into the 1.5 minus epsilon. Yeah, so we are done with
this first implication. So this second implication
is a bit complicated, and I’m not going
to talk about it. So let’s look at this. So I’ll briefly
sketch what happens with this third
implication, basically how KOS bound implies
place n to the 0.5 minus epsilon bound of the generalized
central limit theorem. So formally, this is the
theorem we want to prove. So assume the KLS is bounded
by into the 1/4 minus 1/2 of epsilon, for some
constant epsilon. And let PQ be isotropic
log concave measures in RN and independent
vectors x, y from p, and G from the variance
n normal distribution. Then we have this bound under
generalized central limit constant. So the proof idea
is the following. So here we have two different
isotropic log-concave measures. So ideally, you want to make
one of these a Gaussian, and then use classical
central limit theorem for convex bodies. So roughly, what we want to
show is that the W2 distance between this thing, and being
a product of x with a Gaussian vector, with a standard
Gaussian vector– this is small. And then, if we can show this,
I’m claiming this is done. Because somehow we
can kind of believe that the inner product of the
isotropic log-concave measure and a Gaussian vector should
be close to a real Gaussian random variable by classical
central limit theorem. I’m not going to do
that calculation, but this bound is pretty small. And so let’s see how to prove
the prove the W2 distance between these two quantities. So roughly, the idea is to use
the stochastic localization scheme, which I’m not
going to go into details, but roughly, what
is this doing is, it kind of embeds
the random variable x into a Brownian motion using
Stochastic localization so that we can write x
as the integration of some covariance matrix
times the Brownian motion. And then we can express the– so using this formula, we
can express the inner product of x and y as a
one-dimensional Brownian motion with this factor,
squared off y transpose 80y. 80 is some x some
covariance matrix of the stochastic
localization scheme. I didn’t– yeah I kind
of hide those details. Yeah it’s a bit hard to
explain that carefully. Yeah, so the rough
idea is that– so what’s the
advantage of writing something really simple as
a very complicated thing? So the advantage it is that,
we observe that we can also write x, the inner product
x, and the Gaussian vector g in the same form where
we’ve placed y by g. And the observation
is that, since y is isotropic
log-concave, Gaussian’s isotropic log-concave,
both of these quantities are concentrated around
this mean process, with control factor square
root of trace of 80 squared. So then this gives us a
way to compare to compare both these quantities. So we want to
compare them, right? It’s hard to compare
with them directly. The way to compare them is to
compare both with this quantity L, which is kind of the
mean Gaussian Process. And yeah so, roughly,
what we can do is, we compare the inner product
of x and y with this random variable L. And we can use some
theorem from the Lee-Vempala result on KLS constant
to show that the– like the operator
norm of this matrix is bounded up to some time t. And so the right
hand side we can bound as the fourth moment
of the KLS constant. AUDIENCE: Remind me what
the stochastic localization scheme is? HAOTIAN JIANG: So
roughly, you start with– you start with this, so we have
a target, probably, measure. So you start with
this measure and apply a kind of linear steps, random
linear steps, to this measure. Yeah kind of, it’s a
bit hard to describe. AUDIENCE: [INAUDIBLE] HAOTIAN JIANG: But essentially,
what you are doing is, you are introducing a Gaussian
factor inside the density function. AUDIENCE: So you’re
interpolating– are you interpolating
between this measure and the Gaussian measure? HAOTIAN JIANG: Yes. Yeah, kind of. AUDIENCE: So at time
0, you’re [INAUDIBLE] HAOTIAN JIANG: I time 0
is your target measure. And at time infinity, you
have a huge Gaussian term, which makes you a needle. AUDIENCE: [INAUDIBLE]
you now go back to this, and the expression of your inner
product as a previous slide? HAOTIAN JIANG: OK. AUDIENCE: OK, so the
first line, so now x here, you’re writing x as the integral
from 0 to infinity of At Wt. HAOTIAN JIANG: Right, yeah. AUDIENCE: So I’m
just saying, when you sum up all these
increments, you get a sample from redistribution? HAOTIAN JIANG: Sorry, when I? AUDIENCE: When you sum up all
increments and integrate them? You get a sample
from redistribution. HAOTIAN JIANG: Yes, yeah. Exactly. AUDIENCE: I’m just
trying to square that with what you said about
the localization scheme. HAOTIAN JIANG: OK, OK, Yeah. If you go to
infinity, then you get a sample of your distribution. AUDIENCE: How is this
n dimensional thing become a one-dimensional thing? HAOTIAN JIANG: Oh, so basically,
all these are kind of, like, so they have
the correct variance. They’re all Brownian motion. If you think about
one incremental step– let’s say 80 is
fixed, like, basically then the variance
of this is exactly this square of this times dt. AUDIENCE: So what I was
trying to say [INAUDIBLE].. If you look at the
first integral, there’s an inner product
between y and att yt. At is self-adjoint. So move it over, so
it’s multiplying the y. And now you’re just taking
some fixed vector inner product with the Gaussian vector. And so the law only
depends on the norm. HAOTIAN JIANG:
Sorry, I feel this– I made a mistake here. This should be At squared. Yeah. It should be At squared. All those should be At squared. Yeah, so this is [INAUDIBLE]. This is At squared, At
squared, At squared. And then you get this trace
of [INAUDIBLE] squared. Yeah sorry, I apologize. AUDIENCE: James [INAUDIBLE] HAOTIAN JIANG:
And then, this, we use some bound from
Lee-Vempala to show that, kind of, this integration you
can bound the operator norm up to some time t. And then you can bound the
right hand side by psi n to the fourth moment
of KLS constant. And that’s how you get
this O to the n to the n to the 1 minus 2 epsilon. This is the KLS constant– yeah. Yeah, so OK. So to summarize, we
introduced this notion of generalized
central limit theorem. And recall what this is saying. It’s saying that
the inner product of isotropic log-concave
vectors are W2 close to Gaussian distribution. And we showed the
quantitative of connection that the generalized central
limit constant is roughly the KLS constant squared. And kind of the current KLS
bound doesn’t really improve, doesn’t really give
anything non-trivial about generalized central limit. So it’s kind of still open. So kind of a future
direction is how we get some better bound on
the generalized central limit theorem to make it a real
generalized central limit theorem. But it turns out that,
by our connection, this is really asking how you
prove the KLS bound, which is pretty hard. OK, that’s everything. Thank you. Any questions? AUDIENCE: So I’m just
asking about KLS conjecture. If you look at the Markov
chain, and, let’s say, I have a convex body. You look at the Markov chain
maybe from every point you, and go in and ball around it,
and move at a random point or something like. Does it– HAOTIAN JIANG: [INAUDIBLE] AUDIENCE: Yeah probably,
but does it imply that– does that Markov
chain conjecture to have a second eigenvalue
spectral constant or something like that? HAOTIAN JIANG: Oh. Yeah sorry, I’m
not very familiar with that random log
on the convex bodies. Ask the internet. AUDIENCE: If you took
the right [INAUDIBLE].. AUDIENCE: [INAUDIBLE] AUDIENCE: I’m not
sure I think that. AUDIENCE: You need to make
the body isotropic first, and then just do a
random [INAUDIBLE].. Over the steps– AUDIENCE: How about
the cube root? AUDIENCE: It will be almost
the same as this [INAUDIBLE].. Because if you sample
from [INAUDIBLE].. AUDIENCE: From the cube side. Because all I want
to do is, I want to– we go only around standard
basis vectors in a cube. AUDIENCE: If your step
size is small enough, then the two processes
is almost equivalent, so. AUDIENCE: But the thing about
this which is interesting is, this is like
this some sort of– like it’s not [INAUDIBLE]. It’s sort of a
[INAUDIBLE] of this. OK. So then we get a [INAUDIBLE]. AUDIENCE: As Jim pointed
out, the statements of the generalized one,
because it’s using [INAUDIBLE],, doesn’t itself locally
get the total variation. But, so am I correct in saying
that, the bounds that you get for the two, you
can prove that they are related as a result of this
whole chain of equivalences? HAOTIAN JIANG: Sorry,
which page are you? AUDIENCE: So I mean,
the original one is just stated in terms
of total variation where one must [INAUDIBLE]
Gaussian, basically. And one was an
arbitrary log-concave. So this one doesn’t– Wasserstein doesn’t– I mean,
it’s not saying something total variation, or does it imply
locally on a per-distribution basis, or? AUDIENCE: So I’m not sure
I understand the question. I think the generalized wouldn’t
be true for total variation. The same [INAUDIBLE]. AUDIENCE: So for the
concave distribution, almost all these things
is equivalent, up to log. AUDIENCE: And you guys stated
in Wasserstein [INAUDIBLE].. AUDIENCE: It’s just
because we tried to make the proofs simpler. HAOTIAN JIANG: I
guess we can proved that for like– so the
covariance distance version is saying that I first sample from
one distribution, fix that one, and then look at the marginal
of the other to that direction. Yeah, like there’s
something– we can prove something similar for that. AUDIENCE: Oh, you can. OK. HAOTIAN JIANG: Yeah, yeah. But I forgot what
the bound is there. Yeah, any other questions? Good. Thank you.

Leave a Reply

Your email address will not be published. Required fields are marked *