# Localization schemes: A framework for proving mixing bounds for Markov
chains

Yuansi Chen and Ronen Eldan Duke University.Microsoft Reseach. This work was
partially supported by a European Research Council Grant no. 803084. and by
NSF grant no. DMS-1926686.

###### Abstract

Two recent and seemingly-unrelated techniques for proving mixing bounds for
Markov chains are: (i) the framework of Spectral Independence, introduced by
Anari, Liu and Oveis Gharan, and its numerous extensions, which have given
rise to several breakthroughs in the analysis of mixing times of discrete
Markov chains and (ii) the Stochastic Localization technique which has proven
useful in establishing mixing and expansion bounds for both log-concave
measures and for measures on the discrete hypercube. In this paper, we
introduce a framework which connects ideas from both techniques. Our framework
unifies, simplifies and extends those two techniques. In its center is the
concept of a “localization scheme” which, to every probability measure on some
space $\Omega$, assigns a martingale of probability measures which “localize”
in space as time evolves. As it turns out, to every such scheme corresponds a
Markov chain, and many chains of interest appear naturally in this framework.
This viewpoint provides tools for deriving mixing bounds for the dynamics
through the analysis of the corresponding localization process.
Generalizations of concepts of Spectral Independence and Entropic Independence
naturally arise from our definitions, and in particular we recover the main
theorems in the spectral and entropic independence frameworks via simple
martingale arguments (completely bypassing the need to use the theory of high-
dimensional expanders). We demonstrate the strength of our proposed machinery
by giving short and (arguably) simpler proofs to many mixing bounds in the
recent literature. In particular, we: (i) Give the first $O(n\log n)$ bound
for mixing time of the hardcore-model (of arbitrary degree) in the tree-
uniqueness regime, under Glauber dynamics, (ii) Give the first optimal mixing
bounds for Ising models in the uniqueness regime under any external fields,
(iii) Prove a KL-divergence decay bound for log-concave sampling via the
Restricted Gaussian Oracle, which achieves optimal mixing under any
$\exp\left(n\right)$-warm start, (iv) Prove a logarithmic-Sobolev inequality
for near-critical Ferromagnetic Ising models, recovering in a simple way a
variant of a recent result by Bauerschmidt and Dagallier.

###### Contents

  1. 1 Introduction
    1. 1.1 Review of the framework and ideas
    2. 1.2 Related techniques
  2. 2 Localization schemes and their associated dynamics
    1. 2.1 Simple examples of localization schemes
      1. 2.1.1 Example 1: Coordinate-by-coordinate localization
      2. 2.1.2 Example 2: Random-subspace localization
      3. 2.1.3 Example 3: Halfspace-bisection localization
      4. 2.1.4 Example 4: Gaussian channel localization
      5. 2.1.5 Example 5: Subset simplicial-complex localization
    2. 2.2 Dynamics associated with a localization scheme
    3. 2.3 Doob localization schemes
    4. 2.4 Linear-tilt-localizations
      1. 2.4.1 An alternative viewpoint on the coordinate-by-coordinate localization
      2. 2.4.2 Stochastic localization driven by a Brownian motion
      3. 2.4.3 Stochastic localization and sampling via a restricted Gaussian oracle
      4. 2.4.4 The Negative-Fields localization
      5. 2.4.5 General linear-tilt localizations
    5. 2.5 Spectral gap and modified log-Sobolev inequalities
  3. 3 Approximate conservation of variance and entropy
    1. 3.1 Approximate conservation of variance for linear-tilt localizations and spectral independence
      1. 3.1.1 The case of stochastic localization; bounds for the spectral gap of log-concave measures
    2. 3.2 Approximate conservation of entropy
      1. 3.2.1 Entropic stability
      2. 3.2.2 The case of the coordinate-by-coordinate localization: Entropic independence
      3. 3.2.3 Entropic decay for stochastic localization
      4. 3.2.4 Entropic decay for the negative-fields localization
    3. 3.3 Entropic stability via spectral independence
  4. 4 Annealing via a localization scheme
  5. 5 Applications
    1. 5.1 Glauber dynamics for Ising models
      1. 5.1.1 Mixing under a spectral condition on the interaction matrix
      2. 5.1.2 Near-critical ferromagnetic Ising models
      3. 5.1.3 Graphical Ising model in the uniqueness regime
    2. 5.2 Sampling from strongly log-concave measures via a Restricted Gaussian Oracle
    3. 5.3 A spectral-independence based condition for fast mixing and applications to sampling from the hardcore model
      1. 5.3.1 Application to an optimal mixing bound for Glauber dynamics in the hardcore model
      2. 5.3.2 Properties of the hardcore distribution
  6. 6 Entropic stability via spectral independence
  7. A Appendix A: Loose ends
    1. A.1 Supermartingality of the Dirichlet form: Proof of Proposition 48
    2. A.2 Existence and entropic decay of the negative-fields localization process
    3. A.3 Proofs of technical lemmas from Section 6
  8. B Appendix B: Entropic stability for Ising models under a spectral condition
  9. C Appendix C: The hardcore model

##  1 Introduction

Suppose that we would like to sample from a measure $\nu$ on some set
$\Omega$. For the sake of discussion, suppose that either
$\Omega=\\{-1,1\\}^{n}$ is the Boolean hypercube or $\Omega=\mathbb{R}^{n}$. A
common algorithm is to find a Markov chain whose stationary distribution is
$\nu$ and which exhibits good _mixing bounds_.

In the case $\Omega=\\{-1,1\\}^{n}$, a very useful Markov chain associated to
a measure $\nu$ is the Glauber dynamics, defined as follows: Given
$x\in\\{-1,1\\}^{n}$, the transition kernel from $x$, $P_{x\to~{}\cdot}$, is
the law which describes the point $Y$ picked according to following random
procedure: Pick uniformly a coordinate $i\in[n]$ and then take $Y$ according
to the law $\nu$ conditioned on the event $\left\\{Y_{j}=x_{j},~{}\forall
j\in[n]\setminus\\{i\\}\right\\}$.

For a Markov chain $(X_{t})_{t}$ in a state space $\Omega$ which has a unique
stationary measure $\nu$, a mixing bound typically asserts that for every
$\varepsilon>0$ there is a time $t(\varepsilon)$ such that for all measurable
$A\subset\Omega$ and all $t>t(\varepsilon)$, one has
$\left|\mathbb{P}(X_{t}\in A)-\nu(A)\right|\leq\varepsilon$. See [LP17] for an
extensive account of this subject.

In recent years, there appeared two seemingly-unrelated new techniques which
were used to establish mixing bounds through functional inequalities:

  * •

The work [ALOG20] put forth the notion of _Spectral independence_ and
developed a framework which relies on those notions in order to establish
mixing bounds for measures on the set of subsets of $[n]$. This framework
relies on the theory of high-dimensional expanders. Some follow-up works which
extended this technique are [AJK+21b, CLV21, AJK+21a, CFYZ21b, FGYZ21, BCC+22,
Liu21, AASV21].

  * •

The _stochastic localization_ technique, introduced by the second author in
[Eld13], is the central ingredient used in the proofs of several functional
inequalities, both in the continuous setting where $\Omega=\mathbb{R}^{n}$ and
$\nu$ is a _logarithmically-concave_ measure and in the setting of the
discrete hypercube. Most notably, the technique gives the state-of-the-art
bounds, due to the first author ([Che21]), for the so-called Kannan-Lovász-
Simonovits conjecture ([KLS95a]) and Bourgain’s slicing problem (see [KM21]).
Some follow-up works based on this technique are [Eld20, ES22, Kla18, LV17,
Che21].

In this work, we both unify and expand these two techniques towards a new
framework which can be used to establish mixing bounds in various settings,
showing that the same principles govern in a wide variety scenarios.

One of the main principles underlying both techniques is that concentration
bounds on a measure can be deduced from bounds on the covariance structure of
a certain family of measures which are transformations of the original
measure: In the spectral independence framework, a sufficient condition for a
spectral gap is the boundedness of the _influence_ matrices of restrictions of
the measure (the influence matrix has a simple correspondence with the
covariance matrix), and in the stochastic localization framework a spectral
gap is implied by the boundedness of the covariance matrix along a certain
stochastic process which is associated with the measure.

This work shows that with the correct point of view, those two reductions
follow from the exact same argument. By approaching the notions of spectral
and entropic independence from this point of view, we will be able to:

  1. (i)

Generalize the theory, giving rise to a natural family of Markov chains
together with a toolbox of ingredients that can be used to prove mixing bounds
for those chains.

  2. (ii)

Simplify the proofs in the foundations of the framework of spectral and
entropic independence, and in particular completely bypass the need to use the
theory of high-dimensional expanders.

  3. (iii)

Provide a self-contained and (arguably) simpler proofs for many of the
expansions of the spectral/entropic independence machinery, and in particular
reprove in a more general context several main theorems which appear in
[ALOG20, CLV21, AJK+21b, AJK+21a, CFYZ21b, CFYZ21a, STL20, LST21].

#### Summary of applications

To demonstrate the strength of our machinery, we apply it in several settings:

  * •

We derive the optimal mixing rate for Glauber dynamics on the hardcore model
of any degree in the tree-uniqueness regime, showing that it mixes in time
$O(n\log n)$. A similar mixing rate was obtained in [AJK+21a] for a different
Markov chain which was tailored for the hardcore model. Additionally, our
framework (arguably) allows us to significantly simplify the argument.

  * •

We give the first optimal mixing bounds for graphical Ising models in the
uniqueness regime under any external fields, improving the results in
[CFYZ21a] in the sense that there is no dependence of the bound on the
external field. In this case as well, the proof is significantly simpler.

  * •

Provide a very simple proof of a KL-divergence decay bound for log-concave
sampling via the so-called Restricted-Gaussian-Oracle introduced in [STL20].
Our bound works under any $\exp(n)$-warm start, resolving an issue raised in
[LST21].

  * •

Give a self-contained and simpler proof of mixing for the Glauber dynamics for
Ising models whose interaction matrix has operator norm bounded by $1$, which
in particular gives optimal mixing for Glauber dynamics on the Sherrington-
Kirkpatrick model in high enough temperature, recovering the result derived
from [EKZ21, AJK+21a].

  * •

We recover, in a simple way, a variant of a recent result by Bauerschmidt and
Dagallier [BD22], proving a logarithmic-Sobolev inequality for Ferromagnetic
Ising models in terms of the model’s susceptibility.

#### Concurrent work

Shortly before submitting this manuscript, we were informed by Chen, Feng, Yin
and Zhang of a manuscript in preparation [CFYZ22] which independently proves
parts of the results regarding antiferromagnetic Ising models that we prove
here, and in particular gives the same mixing bound for the hardcore model,
using a different proof technique.

#### Mixing via functional inequalities

Consider a reversible transition operator $P=P_{x\to y}$ with stationary
measure $\nu$ on a state space $\Omega$. Its spectral gap is defined as the
quantity

$\mathfrak{gap}(P):=\inf_{\varphi:\Omega\to\mathbb{R}}\frac{\int_{\Omega\times\Omega}(\varphi(x)-\varphi(y))^{2}dP_{x}(y)d\nu(x)}{2\mathrm{Var}_{\nu}[\varphi]}.$

Next, define

$\mathrm{Ent}_{\nu}[f]=\int f(x)\log f(x)d\nu(x)-\int
f(x)d\nu(x)\log\left(\int f(x)d\nu(x)\right).$

We define the modified log-Sobolev Inequality (MLSI) coefficient as

$\mathrm{\rho_{LS}}(P):=1-\sup_{f:\Omega\to[0,\infty)}\frac{\mathrm{Ent}_{\nu}[Pf]}{\mathrm{Ent}_{\nu}[f]}.$

######  Remark 1.

The above definition is only valid if the Markov transition kernel $P$ is
reversible (or self adjoint). If it is not reversible, $Pf$ needs to be
replaced by $\frac{dP^{*}(f\nu)}{d\nu}$. In this work we only discuss the
reversible case, so we stick to the simpler notation.

It is standard to deduce mixing bounds for the associated Markov chain from
the above quantities. Given an initial distribution $\mu$ which is absolutely
continuous with respect to $\nu$, consider the total-variation mixing time

$t_{\mathrm{mix}}(P,\varepsilon;\mu)=\min\left\\{t>0;~{}~{}\left|P^{t}[\mu](A)-\nu(A)\right|\leq\varepsilon,~{}~{}\forall
A\subset\Omega\right\\}$

Moreover, define

$t_{\mathrm{mix}}(P,\varepsilon)=\max_{x\in\Omega}t_{\mathrm{mix}}(P,\varepsilon,\delta_{x}).$

The following fact is standard (see e.g. [LP17, Theorem 12.4] and [CLV21, Fact
3.5]).

######  Fact 2.

Suppose that for all $x\in\Omega$ one has $\nu(\\{x\\})\geq\eta$. Then,

$\displaystyle t_{\mathrm{mix}}(P,\varepsilon)$ $\displaystyle\leq
C\mathfrak{gap}(P)^{-1}\left(\log(1/\eta)+\log(1/\varepsilon)\right),\text{
and }$ $\displaystyle t_{\mathrm{mix}}(P,\varepsilon)$ $\displaystyle\leq
C\mathrm{\rho_{LS}}(P)^{-1}\left(\log\log(1/\eta)+\log(1/\varepsilon)\right).$

The main aim of our machinery is to provide tools which give lower bounds for
the spectral gap and modified log-Sobolev coefficient for a family of Markov
chains that arise naturally in our framework.

###  1.1 Review of the framework and ideas

We now give a brief overview of the framework constructed in the next
sections.

  * •

The key definitions in the framework are a localization process and a
localization scheme. A localization process is a stochastic process
$(\nu_{t})_{t\geq 0}$ where each $\nu_{t}$ is a probability measure on some
space $\Omega$, having the property that for every subset $A\subset\Omega$,
the stochastic process $t\to\nu_{t}(A)$ is a martingale which satisfies
$\lim_{t\to\infty}\nu_{t}(A)\in\\{0,1\\}$. A localization scheme is a mapping
which, to every probability measure $\nu$ on $\Omega$, assigns a localization
process $(\nu_{t})_{t}$ with $\nu_{0}=\nu$. Thus, a localization scheme can be
thought of as a way to interpolate between a given measure $\nu$ and a
(random) Dirac measure, via a martingale on the space of measures.

  * •

Given a localization process $(\nu_{t})_{t}$ and a time $\tau>0$, there is a
reversible Markov chain on $\nu$, whose stationary measure is $\nu=\nu_{0}$,
which is naturally associated to the localization process. This Markov chain
is defined by the formula

$P_{x\to y}=\mathbb{E}\left[\frac{\nu_{\tau}(x)\nu_{\tau}(y)}{\nu(x)}\right].$

It turns out that many Markov chains arise via naturally defined localization
schemes. In particular, the Glauber dynamics on
$\left(\\{-1,1\\}^{n},\nu\right)$ can be derived from what we call the
coordinate-by-coordinate localization scheme. This scheme is defined by taking
$(k_{1},...,k_{n})$ to be a uniformly random permutation of $[n]$, taking
$X\sim\nu$ and setting $\nu_{t}$ to be the law of $X$ conditioned on
$X_{k_{1}},\dots,X_{k_{t}}$. Some other chains that arise via this framework
(using other localization schemes) are the hit-and-run walk, the up-down walk,
the Restricted-Gaussian dynamics and the field dynamics.

  * •

Next, we will see that there is a simple way to analyze the spectral gap and
MLSI coefficient of the Markov chain associated to a localization scheme: In
order to give a bound on the spectral gap, one needs to give a lower bound to
the quantity
$\mathbb{E}\left[\frac{\mathrm{Var}_{\nu_{\tau}}[\varphi]}{\mathrm{Var}_{\nu}[\varphi]}\right]$
for an arbitrary test function $\varphi:\Omega\to\mathbb{R}$. Similarly, for
MLSI, one needs to lower bound the quantity
$\mathbb{E}\left[\frac{\mathrm{Ent}_{\nu_{\tau}}[f]}{\mathrm{Ent}_{\nu}[f]}\right]$
for $f:\Omega\to[0,\infty)$. Intuitively speaking, the measure-valued process
$\nu_{t}$ “zooms in” on smaller and smaller portions of $\Omega$, and we want
to establish that there is still some variance (or entropy) left all the way
up to time $\tau$, while the measure $\nu_{\tau}$ is already focused on a
small portion of the space.

  * •

In light of the above intuition, it makes sense to analyze the time
differentials of the stochastic processes
$t\to\log(\mathrm{Var}_{\nu_{t}}[\varphi])$ and
$t\to\log(\mathrm{Ent}_{\nu_{t}}[f])$ (which can be in either continuous or
discrete time, depending on the localization scheme). Roughly speaking, we
want to obtain lower bounds for their drifts. By integrating those bounds with
respect to time, we could then obtain bounds on the spectral gap and MLSI.
When a measure $\nu$ satisfies the lower bound
$\frac{d\mathrm{Var}_{\nu_{t}}[\varphi]}{\mathrm{Var}_{\nu_{t}}[\varphi]}\geq-\alpha
dt+\mbox{martingale}$, we say that it satisfies $\alpha$-approximate
conservation of variance bound, and similarly when
$\frac{d\mathrm{Ent}_{\nu_{t}}[f]}{\mathrm{Ent}_{\nu_{t}}[f]}\geq-\alpha
dt+\mbox{martingale}$, we say that it satisfies $\alpha$-approximate
conservation of entropy.

  * •

It turns out that there is an efficient way to obtain approximate conservation
of variance and entropy bounds for a family of localization schemes which we
call linear-tilt localizations. Roughly speaking, these are schemes where
$\frac{\nu_{t+h}}{\nu_{t}}$ is a linear function up to $o(h)$. We will see
that many localization schemes of interest, including the coordinate-by-
coordinate scheme and the stochastic localization scheme of [Eld13] can be
described this way.

$\mu_{0}$$\mu_{1}$$P$$P$$\mu_{k}$$\mu_{k+1}$$P^{k-1}$$\nu$$\mu_{k,t}$$\nu_{t}$localization$\mathrm{E}nt_{\nu}(f)\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\approx\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathbb{E}[\mathrm{E}nt_{\nu_{t}}(f)]\ \ $$\mathrm{E}nt_{\nu}(Pf)\ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \geq\ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\mathbb{E}[\mathrm{E}nt_{\nu_{t}}(Pf)]\ \ $MLSI of
$\displaystyle\nu_{t}$$(a)$$(b)$approximate conservation of
entropysupermartingale${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}?}$
Figure 1: $(a)$. Probability measures encountered during the iterates of a
Markov chain $P$ with target distribution $\nu$ and initial distribution
$\mu_{0}$. We wish to establish the entropy decay (or MLSI) for each iteration
of the Markov chain. $(b)$. Probability measures generated via a localization
scheme. If a stochastic scheme is used, the red box indicates that one may
generate multiple random instances of $(\nu_{t},\mu_{k,t})$ starting from
$(\nu,\ \mu_{k})$. The localization scheme is designed such that it is easier
to establish the entropy decay for the new measures on $(b)$. With
$f=\frac{\mu_{k}}{\nu}$, the entropy decay properties of the measures on $(b)$
can be related to those on $(a)$ thanks to the martingale properties of the
localization.

  * •

For linear-tilt localization scheme, we see that a simple argument which uses
the Cauchy-Schwartz inequality shows that approximate variance conservation is
related to the process of covariance matrices $t\to\mathrm{Cov}(\nu_{t})$. For
the case of coordinate-by-coordinate localization this argument recovers the
spectral independence framework of Anari, Liu and Oveis Gharan in a very
simple way that completely bypasses the need to use high-dimensional
expanders.

  * •

Approximate conservation of entropy turns out to follow from a natural
condition that we call entropic stability, which roughly says that the center
of mass of the measure cannot move too much under perturbations with small
relative entropy. This can be thought of as a weak form of transportation-
entropy inequalities. In the context of the coordinate-by-coordinate
localization we will see that it amounts to a very simple property of the
logarithmic Laplace transform which is very similar to fractional log-
concavity. This would give us a way to recover a variant of the entropic-
independence framework introduced in [AJK+21b].

  * •

Another ingredient in our framework will be the concept of annealing via a
localization scheme. Given two localization schemes on the same space, we can
“concatenate” them by running one scheme up to some time $t$ and then running
the other on the measure $\nu_{t}$ produced by the first scheme. What we will
see is that we can produce spectral gap and MLSI bounds, with respect to the
dynamics associated with the second localization scheme, by showing that the
first localization scheme does not contract the variance / entropy and
“anneals” the measure in a way that it outputs a measure to which we can
ensure mixing for the second scheme. Such annealing procedure will be useful
in many of the applications.

In Figure 1, we summarize the conceptual diagram used to analyze the MLSI
coefficient of a Markov chain via a localization scheme.

###  1.2 Related techniques

#### Local-to-global theorems and high-dimensional expanders

The framework of spectral independence was originally based on _local-
spectral-expansion_ inequalities in high-dimensional expanders, which was
defined and derived in works of Alev, Dinur, Kaufmann, Lau, Mass and Oppenheim
([AL20, Opp18, KO20, DK17, KM17]). These inequalities allow us to compare
between the spectral gap of the $\ell$-down-up-walk and that of the
$\ell+1$-up-down-walk on spectral expanders. This principle was first used
towards establishing bounds on the spectral gap by Anari, Liu, Oveis Gharan
and Vinzant [ALGV19]. Our framework could be thought as an alternative way to
prove “local-to-global” theorems.

#### Pathwise analysis

Our technique can be seen as a manifestation of the pathwise analysis method
(see [Eld22]). This method is closely-related to the so-called _semigroup
technique_ where, in order to prove an inequality regarding a measure, one
considers an evolution of the measure via a semigroup (usually the heat
semigroup) which provides an interpolation between the measure in hand and a
simpler one, and the analysis amounts to showing inequalities regarding the
evolution (e.g., monotonicity of certain quantities). Pathwise-analysis
considers a random evolution rather than a deterministic one which allows
arguments to be carried out path-by-path rather than on an average sense.

#### The logarithmic Laplace transform

The logarithmic Laplace transform is central to our framework: Upper bounds on
either itself or its Hessian turn out to be naturally related to functional
inequalities of the underlying measure, and it is also used associate between
inequalities regarding the center of mass and the covariance structure and
relative entropies. In the context of measures on the discrete cube, it was
suggested that the log-Laplace transform performs a natural role in
concentration inequalities in a paper by Shamir and the second author [ES22].
In the context of log-concave measures on $\mathbb{R}^{n}$ the log-Laplace
transform was long known to perform a central role in concentration
inequalities, see [Kla06, KM12, EK11].

#### Related techniques in Markov chains

Our technique is also related to Markov chain decomposition techniques ([MR02,
JSTV04]) where the analysis of mixing times of a Markov chain is carried out
by splitting the chain into simple-to-analyze components via restriction and
projection-like operations. Another common technique in Markov chains is
_coupling_ , of paths. The coupling technique is also based on path-by-path
analysis but otherwise is very different in spirit from our technique, which
does not consider paths of the random walk but rather of the measure-evolution
process.

#### Localization techniques

The idea of proving concentration inequalities by considering a certain scheme
which converts the measures into simpler ones by localizing on space goes back
to Gromov and Milman [GM87] and Kannan, Lovász and Simonivits ([KLS95b,
KLS95a]). In these works, a measure is effectively decomposed into one-
dimensional components called “needles”. More recently, needle-decompositions
of measures were also used in Riemannian geometry [Kla17, Mil21].

### Summary of notation

  * •

$\mathrm{\rho_{LS}}(\cdot)$ \- Modified log-Sobolev (MLSI) coefficient.

  * •

$\mathfrak{gap}(\cdot)$ \- Spectral gap.

  * •

$\mathrm{Ent}_{\nu}[f]:=\int f(x)\log f(x)d\nu(x)-\int fd\nu\log\left(\int
fd\nu\right)$.

  * •

$\mathrm{D_{KL}}(\mu||\nu):=\int\log\frac{d\mu}{d\nu}(x)d\mu(x)$.

  * •

For a matrix $A\in\mathbb{M}_{n\times n}$, $\|A\|_{\mathrm{OP}}$ \- operator
norm; $\rho(A)$ \- spectral norm.

  * •

For a measure $\nu$ on $\mathbb{R}^{n}$:

    * –

$\mathbf{b}(\nu):=\int xd\nu(x)$ \- The center of mass.

    * –

$\mathrm{Cov}(\nu)=\int(x-\mathbf{b}(\nu))^{\otimes 2}d\nu(x)$ \- The
covariance matrix.

    * –

$\mathbf{Cor}(\nu):=\mathrm{diag}(\mathrm{Cov}(\nu))^{-1/2}\mathrm{Cov}(\nu)\mathrm{diag}(\mathrm{Cov}(\nu))^{-1/2}$,
where $\operatorname{diag}(\cdot)$ is the diagonal matrix obtained by setting
all the off-diagonal entries to $0$, called the correlation matrix.

    * –

$\mathbf{\Psi}(\nu):=\mathrm{Cov}(\nu)\mathrm{diag}(\mathrm{Cov}(\nu))^{-1}$
the influence matrix.

    * –

$\mathcal{T}_{v}\nu$ where $v\in\mathbb{R}^{n}$ is defined as
$\frac{d\mathcal{T}_{v}\nu(x)}{d\nu(x)}:=\frac{e^{\langle
v,x\rangle}d\nu(x)}{\int e^{\langle v,z\rangle}d\nu(z)}$ (exponential tilt of
a measure).

    * –

$(\mathbf{e}_{1},\dots,\mathbf{e}_{n})$ is the standard basis of
$\mathbb{R}^{n}$.

    * –

$\mathbb{S}^{n-1}$ is the unit sphere in $\mathbb{R}^{n}$.

  * •

For a measure $\nu$ on $\\{-1,1\\}^{n}$,

    * –

For $u\in\\{-1,0,1\\}^{n}$ define
$S_{u}:=\bigl{\\{}x\in\\{-1,1\\}^{n};~{}x_{i}u_{i}\geq 0,~{}\forall
i\in[n]\bigr{\\}}$.

    * –

$\mathcal{R}_{u}\nu$ is the normalized restriction of $\nu$ to $S_{u}$
(pinning of $\nu$ according to $u$).

    * –

For $A\subset[n]$, $\mathcal{R}_{A}\nu=\mathcal{R}_{\mathbf{1}_{A}}\nu$ (by
abuse of notation, pinning of coordinates in $A$ to $+1$).

    * –

$P^{\mathrm{GD}}(\nu)$ is the transition kernel for the Glauber-dynamics on
$\nu$.

#### Acknowledgements

R.E. would like to thank Kuikui Liu and Bo’az Klartag for enlightening
discussions. We would also like to thank Kuikui Liu, Mark Sellke and Eric
Vigoda for comments, and Nima Anari and Vishesh Jain for spotting mistakes in
an early version of this paper. This work was carried out when R.E. was on a
fellowship at the Institute for Advanced Study, Princeton.

##  2 Localization schemes and their associated dynamics

In this section, first we introduce the central object in our framework: a
localization scheme. Second we discuss the dynamics associated with a
localization scheme. Finally, we present several examples of localization
schemes.

We fix a set $\Omega$ equipped with a $\sigma$-algebra $\Sigma$. For
simplicity the reader may assume that either $\Omega$ is $\mathbb{R}^{n}$
equipped the $\sigma$-algebra of Lebesgue measurable sets, or $\Omega$ is
$\\{-1,1\\}^{n}$ equipped with the discrete $\sigma$-algebra. Denote by
$\mathcal{M}(\Omega)$ the space of probability measures on $\Omega$.

######  Definition 3.

A localization process on $\Omega$ is a measure-valued stochastic process
$(\nu_{t})_{t\geq 0}$ which satisfies the following properties:

  * (P1)

Almost surely, $\nu_{t}$ is a probability measure on $\Omega$ for all $t$.

  * (P2)

For every measurable $A\subset\Omega$, the process $t\to\nu_{t}(A)$ is a
martingale.

  * (P3)

For any measurable $A\subset\Omega$, the process $\nu_{t}(A)$ almost surely
converges to either $0$ or $1$ as $t\to\infty$.

######  Remark 4.

In the following, we deal with both continuous-time localization processes
(namely the time parameter $t$ lives in $[0,\infty)$) and discrete-time
localization processes (with the discrete time parameter $t=0,1,2,...$). In
order to keep the notation simple, we always assume that $t$ is real-valued,
but in the latter case we simply assume that the process is constant in
intervals of the form $[k,k+1)$ for $k\in\mathbb{Z}$.

######  Definition 5.

A localization scheme on $\Omega$ is a mapping that assigns to each
probability measure $\nu\in\mathcal{M}(\Omega)$ a localization process
$(\nu_{t})_{t\geq 0}$ which satisfies $\nu_{0}=\nu$.

If $\mathcal{L}$ is a localization scheme and $(\nu_{t})_{t\geq
0}=\mathcal{L}(\nu)$, then we say that _$(\nu_{t})_{t\geq 0}$ is the
localization process associated with $\nu$ via the localization scheme
$\mathcal{L}$_.

###  2.1 Simple examples of localization schemes

To better understand the definition of localization schemes, we give a few
simple examples.

####  2.1.1 Example 1: Coordinate-by-coordinate localization

Let $\nu$ be a probability measure on $\\{-1,1\\}^{n}$. Define a process
$\nu_{1},...,\nu_{n}$ in the following way: Let $(k_{1},...,k_{n})$ be a
random variable drawn from the uniform distribution over all permutations of
$[n]$. Let $X$ be a random point sampled from $\nu$, independent of
$(k_{1},...,k_{n})$. For $t\geq 0$, define $\nu_{t}$ to be the law of $X$
conditioned on $X_{k_{1}},...,X_{k_{i}}$ for $i=\min(\lfloor t\rfloor,n)$.

Note that, by definition, the sequence $(\nu_{t})_{t\geq 0}$ is a martingale,
the measures $\nu_{t}$ are probability measures and almost surely $\nu_{t}$ is
a Dirac measure for all $t\geq n$. Thus, $(\nu_{t})_{t}$ is a localization
process. The coordinate-by-coordinate localization scheme is the scheme that
assigns the process $(\nu_{t})_{t\geq 0}$ to the measure $\nu$.

####  2.1.2 Example 2: Random-subspace localization

Let $\nu$ be a probability measure on $\mathbb{R}^{n}$ and let
$(u_{1},...,u_{n})$ be a random orthogonal basis in $\mathbb{R}^{n}$,
distributed according to the Haar measure on the orthogonal group
$\mathrm{O}(n)$. Sample $Z$ a random point from $\nu$ independently of
$(u_{1},...,u_{n})$. For all $t\geq 0$, let $\nu_{t}$ be the law of $Z$
conditioned on $\langle Z,u_{1}\rangle,\dots,\langle Z,u_{i}\rangle$ for
$i=\min(\lfloor t\rfloor,n)$. Then $\nu_{t}$ is a Doob martingale of
probability measures and $\nu_{n}$ is a Dirac point measure supported on $Z$.
Thus, $(\nu_{t})_{t\geq 0}$ is a localization process.

####  2.1.3 Example 3: Halfspace-bisection localization

Let $\nu$ be an absolutely continuous probability measure on $\mathbb{R}^{n}$.
Let $\theta_{1},\theta_{2},\dots$ be a sequence of independent points
generated from the Haar measure on $\mathbb{S}^{n-1}$ and let
$\epsilon_{1},\epsilon_{2},\ldots$ be a sequence of independent $\pm 1$
Bernoulli random variables. Set $\nu_{0}=\nu$ and for all $i\in\mathbb{Z}$,
define $\nu_{i}$ inductively as follows. Set

$t_{i}=\min\left\\{s\in\mathbb{R};~{}~{}\nu_{i-1}(\\{x;~{}x\cdot\theta_{i}\leq
s\\})=1/2\right\\},$

define
$H_{i}=\\{x\in\mathbb{R}^{n};~{}(x\cdot\theta_{i}-t_{i})\epsilon_{i}\geq
0\\}$. For all measurable $A\subset\mathbb{R}^{n}$, set
$\nu_{i}(A):=2\nu_{i-1}(A\cap H)$, the normalized restriction of $\nu_{i-1}$
to $H$. In words, $\nu_{i}$ is generated by choosing a uniformly random
direction in the sphere and picking one of the two half-spaces that bisect
$\nu_{i-1}$ into two parts of equal mass in that direction. Define
$\nu_{t}=\nu_{\min(\lfloor t\rfloor,n)}$. It is not hard to check that this
process is a martingale and thus (P1) and (P2) are satisfied. It can be shown
that (P3) is also satisfies, and so the process $(\nu_{t})_{t}$ is a
localization process, but we omit the proof since this process is only given
for the sake of the example and is not used in the rest of the paper.

####  2.1.4 Example 4: Gaussian channel localization

Consider the case $\Omega=\mathbb{R}^{n}$. Let $\nu$ be a probability measure
on $\Omega$. We construct the process $(\nu_{t})_{t}$ as follows. Let
$X\sim\nu$ and let $B_{t}$ be a standard Brownian motion on $\mathbb{R}^{n}$
independent of $X$. Define $\nu_{t}$ to be the law of $X$ conditioned on
$tX+B_{t}$. This process clearly satisfies (P1) and (P2). Under mild
conditions we have that $\frac{tX+B_{t}}{t}=X+\frac{B_{t}}{t}$ converges to
$X$ and that $(\nu_{t})_{t}$ is a localization process. More details about the
Gaussian channel localization are provided in section 2.4.

####  2.1.5 Example 5: Subset simplicial-complex localization

Let $k$ be an integer less than or equal to $n$. Let $\Omega$ be the set of
all subsets of size of $k$ of $[n]$, and let $\nu$ be a probability measure on
$\Omega$. We construct a sequence of measures as follows: Let $X\sim\nu$ and
let $j_{1},...j_{k}$ be a random permutation of $[k]$, independent of $X$.
Write $X=\\{x_{1},..,x_{k}\\}$, where $x_{1}<\cdots<x_{k}$. For
$i\in\left\\{1,\ldots,k\right\\}$, define $\nu_{i}$ to be the law of $X$
conditioned on $X_{j_{1}},\dots,X_{j_{i}}$. Define $\nu_{t}=\nu_{\lfloor
t\rfloor\wedge k}$.

###  2.2 Dynamics associated with a localization scheme

Given a localization scheme, there is a natural way to introduce a sampling
algorithm associated with it. Specifically, starting from a localization
process associated with $\nu$ with a localization scheme, we can define a
Markov chain whose stationary measure is $\nu$.

######  Definition 6.

(Markov chain associated with a localization process) Let $(\nu_{t})_{t}$ be a
localization process on $\Omega$ and let $\tau>0$. The dynamics associated
with $\nu_{t}$ and $\tau$ is the Markov chain whose transition kernel is
defined by the formula

$P_{x\to
A}=\mathbb{E}\left[\frac{\nu_{\tau}(x)\nu_{\tau}(A)}{\nu(x)}\right],~{}~{}\forall
x\in\Omega,~{}~{}A\subset\Omega.$ (1)

######  Remark 7.

The above definition only makes sense under the condition that $\nu_{t}$ is
almost surely absolutely-continuous with respect to $\nu$, in which case the
quantity $\frac{\nu_{t}(x)}{\nu(x)}$ is well-defined for $\nu$-almost every
$x$. Below, we will see how to remedy this issue if this is not the case.

######  Fact 8.

The operator defined in (1) is the transition kernel of a reversible Markov
chain whose stationary measure is $\nu$.

###### Proof.

By property (P2) of Definition 3, we have $\mathbb{E}[\nu_{\tau}]=\nu$, which
implies that for $\nu$-almost every $x\in\Omega$,

$\mathbb{E}\left[\frac{\nu_{\tau}(x)\nu_{\tau}(\Omega)}{\nu(x)}\right]=\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\right]=1,$

so that $P_{x\to\cdot}$ is indeed a probability measure. It is evident from
the definition that for all $A,B\subset\Omega$,

$\displaystyle\int_{A}P_{x\to B}d\nu(x)$
$\displaystyle=\int_{A}\mathbb{E}\left[\frac{d\nu_{\tau}(x)}{d\nu(x)}\nu_{\tau}(B)\right]d\nu(x)$
$\displaystyle=\mathbb{E}\left[\nu_{\tau}(A)\nu_{\tau}(B)\right]=\int_{B}P_{y\to
A}d\nu(y),$

hence the Markov chain is reversible and has stationary measure $\nu$.

######  Remark 9.

Instead of taking the time $\tau$ to be deterministic, we can take it to be a
_stopping time_. It is not hard to verify that we still get a reversible
Markov chain.

Another interpretation of the Markov chain associated to localization process
is the following: consider a random variable $(X,Y)\in\Omega\times\Omega$
defined by

$\mathbb{P}(X\in A,~{}Y\in
B)=\mathbb{E}\left[\nu_{\tau}(A)\nu_{\tau}(B)\right].$ (2)

Define a transition kernel by the formula

$P_{x\to A}=\mathbb{P}(Y\in A~{}|X=x).$

If $\nu_{t}$ is absolutely continuous with respect to $\nu$, the conditioning
is well-defined for $\nu$-almost every $x$. If that is the case, it is not
hard to check that the above transition kernel coincides with the one in
definition 6.

Definition 6 introduces a Markov chain with a localization process and a
parameter $\tau$. Consequently, every localization scheme gives rise to a
sampling algorithm.

######  Definition 10.

(Sampling algorithm associated to a localization scheme). Given a localization
scheme $\mathcal{L}$ on a space $\Omega$ and given $\tau>0$, we define
$P^{(\mathcal{L},\tau)}$ as the mapping from $\mathcal{M}(\Omega)$ to the
space of Markov kernels on $\Omega$ where $P^{(\mathcal{L},\tau)}(\nu)$ is
given by equation (1).

#### Example 1: The coordinate-by-coordinate scheme and Glauber dynamics

Let us show that the dynamics associated with the coordinate-by-coordinate
localization scheme from subsection 2.1.1, with the choice $\tau=n-1$, is the
Glauber dynamics, defined as follows.

######  Definition 11.

(Glauber dynamics) For a measure $\nu$ on $\\{-1,1\\}^{n}$, the Glauber
dynamics is the Markov chain whose transition kernel $P^{\mathrm{GD}}(\nu)$ is

$\displaystyle P^{\mathrm{GD}}_{x\to
y}(\nu)=\frac{1}{n}\frac{\nu(y)}{\nu(x)+\nu(y)}\mathbf{1}_{\\{\|x-y\|_{1}=1\\}}+p\mathbf{1}_{\\{x=y\\}},$

with
$p=\frac{1}{n}\sum_{i=1}^{n}\frac{\nu(x)}{\nu(x)+\nu(x\oplus\mathbf{e}_{i})}$
and $x\oplus\mathbf{e}_{i}$ denotes the vector of $\left\\{-1,1\right\\}^{n}$
obtaining by flipping the $i$-th coordinate of $x$.

Consider the dynamics obtained from the formula (1) with $\tau=n-1$. First,
for $y=x\oplus\mathbf{e}_{i}$, we have

$\displaystyle\quad\mathbb{E}\left[\frac{\nu_{\tau}(x)\nu_{\tau}(y)}{\nu(x)}\right]$
$\displaystyle=\frac{1}{n}\sum_{j\in[n]}\mathbb{E}\left[\left.\frac{\nu_{n-1}(x)\nu_{n-1}(y)}{\nu(x)}\right|k_{n}=j\right]$
$\displaystyle=\frac{\mathbb{P}(\mathrm{supp}(\nu_{n-1})=\\{x,y\\})}{n}\mathbb{E}\left[\left.\frac{\nu_{n-1}(x)\nu_{n-1}(y)}{\nu(x)}\right|k_{n}=i,\mathrm{supp}(\nu_{n-1})=\\{x,y\\}\right]$
$\displaystyle=\frac{\nu(x)+\nu(y)}{n\nu(x)}\frac{\nu(x)}{\nu(x)+\nu(y)}\frac{\nu(y)}{\nu(x)+\nu(y)}$
$\displaystyle=\frac{1}{n}\frac{\nu(y)}{\nu(x)+\nu(y)}.$

Second, if $\|x-y\|_{1}>1$ then $P^{\mathrm{GD}}_{x\to y}(\nu)=0$, which
establishes the fact that the Markov chain associated with the coordinate-by-
coordinate process is Glauber dynamics.

######  Remark 12.

We can also consider the Markov chain obtained by choosing $\tau=n-\ell$, for
some $\ell>1$. The transition kernel of this Markov chain can be described as
follows: Given that the current state is some $x\in\\{-1,1\\}^{n}$, the next
state will be generated by first choosing a subset of coordinates
$A\subset[n]$ with $|A|=\ell$ uniformly at random, and then choosing a point
according to the restriction of $\nu$ to the subcube defined by
$\\{y;~{}y_{i}=x_{i},~{}~{}\forall i\in[n]\setminus A\\}$. We refer to this
Markov chain as the $\ell$-Glauber-dynamics.

#### Example 2: The subspace localization scheme and the hit-and-run walk

Fix a measure $\nu$ on $\mathbb{R}^{n}$ and let $(\nu_{t})_{t}$ be the
subspace-localization process defined in Subsection 2.1.2. Define $\tau=n-1$.
Let $(X,Y)$ obey equation (2). Given $x\in\Omega$, consider the expression

$\displaystyle P_{x\to A}$ $\displaystyle=\mathbb{P}[Y\in A|X=x]$
$\displaystyle=\mathbb{E}_{u_{1},...,u_{n-1},Z}[\mathbb{P}(Y\in
A|X=x,u_{1},...,u_{n-1},Z)].$

Note that, by definition, conditioned on $u_{1},..,u_{n-1},Z$ we have that
$X,Y$ have the law of the restriction of $\nu$ to $\\{x;~{}\langle
x-Z,u_{i}\rangle=0,~{}~{}\forall i\in[n-1]\\}$. Therefore, we can understand
the conditioning on $X=x$ as conditioning on the event $E_{x}=\\{\langle
Z-x,u_{i}\rangle=0,~{}~{}\forall i\in[n-1]\\}$. In other words

$\displaystyle P_{x\to A}$
$\displaystyle=\mathbb{E}_{u_{1},...,u_{n}}\left[\mathbb{P}\left(Z\in
A|\langle Z-x,u_{i}\rangle=0,~{}\forall i\in[n-1]\right)\right]$
$\displaystyle=\mathbb{E}_{u_{n}}\left[\mathbb{P}\left(Z\in
A|\mathrm{Proj}_{u_{n}^{\perp}}(Z-x)=0\right)\right].$

In words, given the point $x$, to generate the next point in the Markov chain,
we first generate the direction $u_{n}$ uniformly from the Haar measure on the
unit sphere and then generate a point from the restriction of $\nu$ to the
fiber $\mathrm{Proj}_{u_{n}^{\perp}}x+\mathrm{Span}(u_{n})$. This Markov chain
is known as the hit-and-run walk (see e.g, [Lov99]).

#### Other examples of Markov chains

  * •

In Subsection 2.4.3, we show that the Gaussian-channel localization gives rise
to the sampling algorithm introduced in [STL20], where each step is a
restricted Gaussian oracle step.

  * •

The dynamics associated to the subset simplicial-complex localization in
Subsection 2.1.5 with time $\tau=k-\ell$ leads to the $\ell$-down-up walk (see
[ALOG20]).

  * •

A continuous analogue of the coordinate-by-coordinate localization scheme
gives rise to the coordinate hit-and-run algorithm (see [NS22]).

  * •

The dynamics associated with the negative-fields localization constructed in
Subsection 2.4.4 is the field dynamics introduced in [CFYZ21b].

###  2.3 Doob localization schemes

In this subsection, we describe a class of localization schemes which
generalizes several examples we have seen so far. Given a set $\Omega$
equipped with a $\sigma$-algebra $\Sigma$, we say that a filtration
$\left(\mathcal{F}_{t}\right)_{t\geq 0}$ of $\Omega$ is precise if
$\sigma\left(\bigcup_{t\geq 0}\mathcal{F}_{t}\right)=\Sigma$. Let
$\mathbf{F}_{\Omega}$ be the space of probability measures over the set of
precise filtrations on $\Omega$.

Given a distribution $m\in\mathbf{F}_{\Omega}$, we can introduce a
localization scheme using the filtration generated from $m$. For any measure
$\nu$ on $\Omega$, we construct a localization process $(\nu_{t})_{t}$ as
follows: Let $Y$ be a $\nu$-distributed random variable and let
$\mathcal{F}_{t}$ be a precise filtration generated from $m$ independently of
$Y$. $\nu_{t}$ is defined as follows

$\displaystyle\nu_{t}(A)=\mathbb{E}\left[\mathbb{P}(Y\in
A|\mathcal{F}_{t})\right],~{}~{}\forall A\subset\Omega\mbox{ measurable }.$

It is evident that $\nu_{t}$ satisfies (P1) and (P2). Since $\mathcal{F}_{t}$
is precise we also have that $\nu_{t}$ satisfies (P3). We call localization
schemes constructed this way Doob localization schemes.

We can verify that coordinate-by-coordinate scheme and the random-subspace
localization schemes are Doob localization schemes. For the coordinate-by-
coordinate localization scheme, it suffices to take
$\left(\mathcal{F}_{t}\right)_{t\geq 0}$ to be $\sigma$-algebra generated by
the maps $x\mapsto x_{i}$ for $i\in k_{1},\ldots,k_{\left\lfloor
t\right\rfloor}$. For the random-subspace localization scheme, we take
$\left(\mathcal{F}_{t}\right)_{t\geq 0}$ to be $\sigma$-algebra generated by
the maps $x\mapsto\left\langle x,u_{i}\right\rangle$ for $i\in
k_{1},\ldots,k_{\left\lfloor t\right\rfloor}$.

###  2.4 Linear-tilt-localizations

In this subsection, we describe a family of localization schemes which arise
from a process known in the literature under the name stochastic localization.
To avoid confusion and to make it possible to include new localization schemes
to this family, we refer to this family as linear-tilt localizations. The
general idea behind these schemes is that, in order to obtain the measure
$\nu_{t+dt}$ from the measure $\nu_{t}$, one multiplies the density by a
random linear function. Our definitions in this section make sense whenever
$\Omega$ can be naturally embedded in a linear space. However, we will mainly
focus our attention on the cases $\Omega=\mathbb{R}^{n}$ and
$\Omega=\\{-1,1\\}^{n}\subset\mathbb{R}^{n}$.

Given a measure $\nu$ on $\Omega$, denote the center of mass of $\nu$ as
$\mathbf{b}(\nu):=\int_{\Omega}x\nu(dx)$.

####  2.4.1 An alternative viewpoint on the coordinate-by-coordinate
localization

We begin with an alternative description of the coordinate-by-coordinate
localization scheme described in Subsection 2.1.1, which serves as our first
example for a linear-tilt localization.

Fix a measure $\nu$ on $\Omega=\\{-1,1\\}^{n}$. Let $(k_{1},...,k_{n})$ be a
uniform permutation of $[n]$ and let $U_{1},\dots,U_{n}$ be an i.i.d. sequence
of independent random variables drawn from the uniform distribution on
$[-1,1]$.

Define $\nu_{0}=\nu$. For $i=0,1,\dots,n$ define

$\nu_{i+1}(x)=\nu_{i}(x)\bigl{(}1+\left\langle
x-\mathbf{b}(\nu_{i}),Z_{i}\right\rangle\bigr{)}$ (3)

where $Z_{i}$ is defined by

$Z_{i}=\mathbf{e}_{k_{i}}\times\begin{cases}\frac{1}{1+\mathbf{b}(\nu_{i})_{k_{i}}}&\mbox{if}~{}~{}\mathbf{b}(\nu_{i})_{k_{i}}\geq
U_{i},\\\
\frac{-1}{1-\mathbf{b}(\nu_{i})_{k_{i}}}&\mbox{if}~{}~{}\mathbf{b}(\nu_{i})_{k_{i}}\leq
U_{i}.\end{cases}$ (4)

and where $\mathbf{e}_{1},\dots,\mathbf{e}_{n}$ is the standard basis of
$\mathbb{R}^{n}$ . Finally, to extend the process beyond times $1,\dots,n$,
take $\nu_{t}=\nu_{\lfloor t\rfloor\wedge n}$.

To see that this is indeed a localization process, first observe that to
obtain $\nu_{t+1}$, we multiply $\nu_{t}$ by a linear function which is equal
to $1$ at its center of mass, meaning that
$\nu_{t}(\Omega)=\nu_{t+1}(\Omega)$. It is easy to check that
$\mathbb{E}[Z_{t}]=0$, which verifies (P2). Finally, a direct calculation
shows that $\nu_{i+1}$ is in fact a pinning of the $k_{i}$-th coordinate of
$\nu_{i}$. Indeed, if
$x_{k_{i}}=-\operatorname{sign}(U_{i}-\mathbf{b}(\nu_{i})_{k_{i}})$ then
$\left\langle x-\mathbf{b}(\nu_{i}),Z_{i}\right\rangle=-1$ in which case the
right-hand side of (3) vanishes.

It follows from the above that the definition in this subsection is equivalent
to the one given in subsection 2.1.1. This point of view can be used as a
motivation for the family of localization schemes considered in this section:
Note that it is not evident at all from this definition that the described
scheme is a _Doob_ localization scheme. However, in this case $(\nu_{t})_{t}$
can be thought of as a Markov chain on the space of measures, where the
transition corresponds to multiplication by linear functions with random
slopes whose conditional expectation is $0$. In this example, the slopes are
chosen in the unique way so that it will cause the measure $\nu_{t+1}$ to be a
restriction of $\nu_{t}$ to a subcube.

####  2.4.2 Stochastic localization driven by a Brownian motion

Next we describe the stochastic localization process initially constructed in
[Eld13]. Let $\nu$ be a probability measure on $\mathbb{R}^{n}$, and let
$B_{t}$ be a standard Brownian motion in $\mathbb{R}^{n}$ adapted to a
filtration $\mathcal{F}_{t}$. Let $(C_{t})_{t}$ be an
$\mathcal{F}_{t}$-measurable process which takes values in the space of
$n\times n$ positive-definite matrices. We define a process $(\nu_{t})_{t}$
via the change of measure $\frac{d\nu_{t}}{d\nu}(x)=F_{t}(x)$, where the
functions $F_{t}(x)$ solve the following system of stochastic differential
equations:

$F_{0}(x)=1,~{}~{}dF_{t}(x)=F_{t}(x)\langle
x-\mathbf{b}(\nu_{t}),C_{t}dB_{t}\rangle,~{}~{}\forall x\in\mathbb{R}^{n}.$
(5)

The above is an infinite system of differential equations (one for each
$x\in\mathbb{R}^{n}$), but it turns out that a slightly different point of
view allows us to view it as a finite system. The uniqueness and existence of
the solution of the system of stochastic differential equations are
established in [Eld13, EMZ20]. The following fact gives a sufficient condition
for the process to be a localization process. It was proved in [Eld13, EMZ20],
but we provide a sketch for completeness.

######  Fact 13.

If, for every unit vector $\theta\in\mathbb{S}^{n-1}$, one has
$\int_{0}^{\infty}|C_{t}\theta|^{2}dt=\infty$ almost surely, then the process
$(\nu_{t})_{t}$ is a localization process.

###### Proof.

A direct calculation shows that

$\displaystyle d\nu_{t}(\mathbb{R}^{n})$
$\displaystyle=\int_{\mathbb{R}^{n}}dF_{t}(x)\nu(dx)$
$\displaystyle=\int_{\mathbb{R}^{n}}\langle
x-\mathbf{b}(\nu_{t}),C_{t}dB_{t}\rangle F_{t}(x)\nu(dx)$
$\displaystyle=\left\langle\int
xd\nu_{t}-\mathbf{b}(\nu_{t}),C_{t}dB_{t}\right\rangle=0.$

Moreover, by Ito’s formula

$d\log F_{t}(x)=\langle
x-\mathbf{b}(\nu_{t}),C_{t}dB_{t}\rangle-\frac{1}{2}\left|C_{t}(x-\mathbf{b}(\nu_{t}))\right|^{2}dt$

which shows that $F_{t}(x)$ is non-negative almost surely for all $x,t$. The
above establishes (P1). The martingale property (P2) follows directly from
(5). Property (P3) follows from a calculation carried out using Ito’s formula
which shows that
$d\mathrm{Cov}(\nu_{t})=-\mathrm{Cov}(\nu_{t})C_{t}^{2}\mathrm{Cov}(\nu_{t})dt+\mbox{
martingale }$, see [Eld20, Section 2].

A very useful property of the stochastic localization process is the
following.

######  Fact 14.

For every $t\geq 0$, we have almost surely that $\nu_{t}$ attains the form,

$\frac{\nu_{t}(dx)}{\nu(dx)}=\exp\left(Z_{t}-\frac{1}{2}\left\langle\Sigma_{t}x,x\right\rangle+\langle
y_{t},x\rangle\right),$ (6)

where $\Sigma_{t}=\int_{0}^{t}C_{s}^{2}ds$,
$y_{t}=\int_{0}^{t}\left(C_{s}dB_{s}+C_{s}^{2}\mathbf{b}(\nu_{s})ds\right)$
and $Z_{t}$ is a normalizing constant to ensure $\nu_{t}$ is a probability
measure.

This process turns out to be useful in proving concentration inequalities in
both the continuous setting of log-concave measures and the discrete setting,
see [Che21, Eld13, Eld20, ES22, LV17, EKZ21].

####  2.4.3 Stochastic localization and sampling via a restricted Gaussian
oracle

With the specific choice $C_{t}=\mathbf{I}_{n}$, the stochastic localization
scheme gives rise, via equation (1), to a natural reversible Markov chain
associated with a measure on $\mathbb{R}^{n}$, which happens to coincide with
the restricted Gaussian dynamics given in [STL20, LST21].

For a measure $\nu$ on $\mathbb{R}^{n}$, $y\in\mathbb{R}^{n}$ and $\eta>0$,
define the measure $\mathcal{S}_{y,\eta}\nu$ by

$\mathcal{S}_{y,\eta}\nu(dx):=\frac{\nu(dx)\exp\left(-\frac{1}{2\eta}|x-y|^{2}\right)}{\int_{\mathbb{R}^{n}}\exp\left(-\frac{1}{2\eta}|z-y|^{2}\right)\nu(dz)}$

######  Definition 15.

(The restricted Gaussian dynamics) For a measure $\nu$ on $\mathbb{R}^{n}$ and
$\eta>0$, the restricted Gaussian dynamics for $\nu$ with parameter $\eta$ is
the Markov chain defined by

$P^{\mathrm{RGD}_{\eta}}(\nu)_{x\to
A}=\mathbb{E}_{y\sim\mathcal{N}(x,\eta\mathbf{I}_{n})}\left[\mathcal{S}_{y,\eta}\nu(A)\right].$

The next proposition is based on an alternative point of view on stochastic
localization which was suggested by El Alaoui and Montanari [AM21].

######  Proposition 16.

The dynamics associated to the stochastic localization process with
$C_{t}\equiv\mathbf{I}_{n}$ and time $\tau$ is the restricted Gaussian
dynamics of $\nu$ with $\eta=1/\tau$.

###### Proof.

It follows from equation (6) that $\nu_{t}=\mathcal{S}_{y_{t},1/t}\nu$, where
$y_{t}=B_{t}+\int_{0}^{t}\mathbf{b}(\nu_{s})ds$. Define
$X=\lim_{t\to\infty}\frac{1}{t}y_{t}$. It is shown in [Eld20, Section 2] that
$\mathbf{b}(\nu_{t})$ almost-surely converges and that
$\lim_{t\to\infty}\mathbf{b}(\nu_{t})$ has the law $\nu$. Therefore,

$X=\lim_{t\to\infty}\frac{B_{t}}{t}+\frac{1}{t}\int_{0}^{t}\mathbf{b}(\nu_{s})ds=\lim_{t\to\infty}\mathbf{b}(\nu_{t})\sim\nu.$

An application of [AM21, Theorem 2] tells us that $(X,y_{t})$ have the same
joint law as $(X,tX+\sqrt{t}\Gamma)$ where
$\Gamma\sim\mathcal{N}(0,\mathbf{I}_{n})$ is independent of $X$. Therefore, if
we generate the measure $\nu_{t}$ according to the process and then generate
$X^{\prime}$ according to $\nu_{t}$, then the joint law of
$(X^{\prime},\nu_{t})$ is the same as that of
$(X^{\prime},\mathcal{S}_{X+\Gamma/\sqrt{t},1/t}\nu)$. In light of equation
(2), this completes the proof.

The last proposition also shows that the stochastic localization process with
the choice $C_{t}=\mathbf{I}_{n}$ is identical to the Gaussian channel
localization from Subsection 2.1.4.

####  2.4.4 The Negative-Fields localization

In this subsection, we introduce a localization scheme which is only relevant
for the setting $\Omega=\\{-1,1\\}^{n}$. Roughly speaking, the Negative-Fields
localization process associated to a measure $\nu$ on $\\{-1,1\\}^{n}$ is the
unique process $(\nu_{t})_{t}$ where $\nu_{t}$ is almost surely an exponential
tilt of the measure by some deterministic external field $v(t)$, and a random
pinning of the measure.

Before we move on to the construction of the process, let us introduce some
notation. For a measure $\nu$ on $\\{-1,1\\}^{n}$ and for $v\in\mathbb{R}^{n}$
define

$\mathcal{T}_{v}\nu(x)=\frac{e^{\langle x,v\rangle}\nu(x)}{\int e^{\langle
y,v\rangle}d\nu(y)},$

the measure obtained by applying external field $v$ to $\nu$ (or the
exponential tilt).

For $u\in\\{-1,0,1\\}$ we define the $u$-pinning $\mathcal{R}_{u}\nu$ to be
the restriction of $u$ to the subcube

$S_{u}:=\left\\{x\in\\{-1,1\\}^{n};~{}x_{i}u_{i}\geq 0,~{}\forall
i\in[n]\right\\}$

By slight abuse of notation, for $A\subset[n]$ define
$\mathcal{R}_{A}\nu(x)=\mathcal{R}_{\mathbf{1}_{A}}\nu(x)$, namely the measure
$\nu$ where the coordinates in $A$ are pinned to $+1$.

We first give a slightly informal account of the construction. Given an
initial measure $\nu$ on $\Omega$, the negative-fields localization process is
the unique martingale of probability measures, $(\nu_{t})_{t}$, which has the
form

$\nu_{t}=\mathcal{T}_{-t\vec{\mathbf{1}}}\mathcal{R}_{A_{t}}\nu,~{}~{}\forall
t>0,$

where $\vec{\mathbf{1}}=(1,...,1)$ and $(A_{t})_{t}$ is an almost-surely
increasing process of subsets of $[n]$.

A different point of view on the process is to express it as a linear-tilt
localization by noting that both the operation of applying an infinitesimal
external field and that of pinning amount to linear tilts. Hence, we suppose
that for all $t\geq 0$

$\nu_{t+h}(x)=\nu_{t}(x)\left(1+\langle
x-\mathbf{b}(\nu_{t}),Z(t+h)-Z(t)\rangle\right)+o(h),~{}~{}~{}\forall h>0,$
(7)

where

$Z_{i}(t)=-t+\frac{\mathbf{1}\left\\{i\in A_{t+h}\setminus
A_{t}\right\\}}{1+\mathbf{b}(\nu_{t})_{i}}$

and the process $(A_{t})_{t}$ of increasing sets is uniquely defined by the
equation

$\mathbb{P}(i\in A_{t+h}\setminus A_{t}~{}~{}|A_{t})=\mathbf{1}_{\\{i\notin
A_{t}\\}}\bigl{(}1+\mathbf{b}(\nu_{t})_{i}\bigr{)}h+o(h),~{}~{}~{}\forall
h>0.$

The two last equations render that

$\mathbb{E}[Z(t+h)|A_{t}]=Z(t)+o(h),~{}~{}~{}\forall t\geq 0,h>0$

which, as we will see, implies that the process is a martingale.

######  Remark 17.

Roughly speaking, the measure $\nu_{t}$ evolves by applying increasingly
stronger negative external fields to all sites, and occasionally pinning sites
to the value $+1$ in a way that balances the effect of the external fields
resulting in a martingale. The dynamics associated with this localization is
called the field dynamics, and was introduced in [CFYZ21b]. Below, will not
study the field dynamics itself, but we will be able to apply this
localization to obtain the same results in a way that bypass the dynamics.

The next proposition gives a rigorous account of the above and establishes the
existence of a slightly generalized version of the process.

######  Proposition 18.

Let $\nu$ be a probability measure on $\\{-1,1\\}^{n}$ and let
$v:[0,\infty)\to\mathbb{R}^{n}$ be a differentiable curve satisfying $v(0)=0$.
There exists a (unique) stochastic process $(u(t))_{t}$ with
$u_{t}\in\\{-1,0,1\\}^{n}$, such that the process $(\nu_{t})_{t}$ defined by
$\nu_{t}:=\mathcal{R}_{u(t)}\mathcal{T}_{v(t)}\nu$ is a martingale. This
process is uniquely defined by

$\mathbb{E}\bigl{(}\bigl{.}u(t+h)_{i}-u(t)_{i}~{}\bigr{|}u(t)\bigr{)}=-\mathbf{1}_{\\{u(t)_{i}=0\\}}\bigl{(}1-\operatorname{sign}(v_{i}^{\prime}(t))\mathbf{b}(\nu_{t})_{i}\bigr{)}v^{\prime}_{i}(t)h+o(h),~{}~{}\forall
t\geq 0,i\in[n].$

Moreover, we have for all $t\geq 0$ and $x\in\\{-1,1\\}^{n}$,

$\nu_{t+h}(x)=\nu_{t}(x)\left(1+\sum_{i\in[n]}(x_{i}-\mathbf{b}(\nu_{t})_{i})\left(hv_{i}^{\prime}(t)+\frac{u(t+h)_{i}-u(t)_{i}}{1-\operatorname{sign}(v_{i}^{\prime}(t))\mathbf{b}(\nu_{s})_{i}}\right)\right)+o(h).$
(8)

If, in addition, $\lim_{t\to\infty}|v_{i}(t)|=\infty$ for all $i\in[n]$, then
the above process is a localization process.

The proof of this proposition is postponed to Appendix A.

####  2.4.5 General linear-tilt localizations

Let us now consider a natural family of localization processes which
generalizes the two previous examples. Let $\nu_{t}$ be a localization process
on $\Omega\subset\mathbb{R}^{n}$ (in general we can consider any linear
space). Suppose that for every $t\geq 0$ and $h>0$ we can write

$\frac{d\nu_{t+h}}{d\nu}(x)=1+\langle
x-\mathbf{b}(\nu_{t}),Z_{t,h}\rangle+o_{x}(h),$ (9)

such that $\mathbb{E}[Z_{t,h}|\nu_{t}]=0$. In other words, the measure
$\nu_{t+h}$ is generated from $\nu_{t}$ via multiplication by a linear
function whose slope is a conditionally-centered random variable. Note that
the linear functions is equal to $1$ at the center of mass of $\nu_{t}$, which
has to be the case given that $\nu_{t}$ remains a probability measure.

It is not hard to see that the family of localization processes which obey
equation (9) contains the coordinate-by-coordinate localization, the
stochastic localization and the negative-fields localization.

###  2.5 Spectral gap and modified log-Sobolev inequalities

Consider a localization process $(\nu_{t})_{t}$ obtained from $\nu$ via some
localization scheme $\mathcal{L}$, and let $\tau>0$. Let
$P=P^{(\mathcal{L},\tau)}(\nu)$ be the Markov chain obtained by formula (1).
The following result establishes functional inequalities regarding the
transition kernel $P$ through the analysis of the corresponding localization
process.

######  Proposition 19.

If the transition kernel $P$ is the one associated to the localization process
$(\nu_{t})_{t}$ via equation (1), then

$\mathfrak{gap}(P)=\inf_{\varphi:\Omega\to\mathbb{R}}\frac{\mathbb{E}\left[\mathrm{Var}_{\nu_{\tau}}[\varphi]\right]}{\mathrm{Var}_{\nu}[\varphi]},\text{
and }$ (10)
$\mathrm{\rho_{LS}}(P)\geq\inf_{f:\Omega\to[0,\infty)}\frac{\mathbb{E}\left[\mathrm{Ent}_{\nu_{\tau}}[f]\right]}{\mathrm{Ent}_{\nu}[f]}.$
(11)

###### Proof.

For a test function $\varphi:\Omega\to$, we have

$\displaystyle\int_{\Omega}\varphi(x)\left(\int_{\Omega}\varphi(y)dP_{x}(y)\right)d\nu(x)$
$\displaystyle=\int_{\Omega}\varphi(x)\left(\mathbb{E}\left[\frac{\nu_{\tau}(x)\left(\int_{\Omega}\varphi(y)d\nu_{\tau}(y)\right)}{\nu(x)}\right]\right)d\nu(x)$
$\displaystyle=\mathbb{E}\left[\int_{\Omega}\varphi(x)d\nu_{\tau}(x)\left(\int_{\Omega}\varphi(y)d\nu_{\tau}(y)\right)\right]$
$\displaystyle=\mathbb{E}\left[\left(\int_{\Omega}\varphi(x)d\nu_{\tau}(x)\right)^{2}\right].$

Consequently,

$\displaystyle\frac{\int_{\Omega\times\Omega}(\varphi(x)-\varphi(y))^{2}dP_{x}(y)d\nu(x)}{2\mathrm{Var}_{\nu}[\varphi]}$
$\displaystyle=\frac{\int_{\Omega}\varphi(x)^{2}d\nu(x)-\mathbb{E}\left[\left(\int_{\Omega}\varphi(x)d\nu_{\tau}(x)\right)^{2}\right]}{\mathrm{Var}_{\nu}[\varphi]}$
$\displaystyle=\frac{\mathbb{E}\left[\int_{\Omega}\varphi(x)^{2}d\nu_{\tau}(x)-\left(\int_{\Omega}\varphi(x)d\nu_{\tau}(x)\right)^{2}\right]}{\mathrm{Var}_{\nu}[\varphi]}$
$\displaystyle=\frac{{\mathbb{E}}\left[\mathrm{Var}_{\nu_{\tau}}[\varphi]\right]}{\mathrm{Var}_{\nu}[\varphi]}.$

Taking the infimum over all $\varphi$, we obtain (10). For the MLSI, observe
that by Jensen’s inequality we have for all $x\in\Omega$ and all
$f:\Omega\to\mathbb{R}_{+}$,

$\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\int_{\Omega}f(y)d\nu_{\tau}(y)\right]\log\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\int_{\Omega}f(y)d\nu_{\tau}(y)\right]$
$\leq\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\log\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\right)\right)\right],$

where we used the fact that
$\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\right]=1$. We therefore have

$\displaystyle\quad\int_{\Omega}(Pf)(x)\log((Pf)(x))d\nu(x)$
$\displaystyle=\int_{\Omega}\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\int_{\Omega}f(y)d\nu_{\tau}(y)\right]\log\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\int_{\Omega}f(y)d\nu_{\tau}(y)\right]d\nu(x)$
$\displaystyle\leq\int_{\Omega}\mathbb{E}\left[\frac{\nu_{\tau}(x)}{\nu(x)}\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\log\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\right)\right)\right]d\nu(x)$
$\displaystyle=\mathbb{E}\left[\left(\int_{\Omega}\nu_{\tau}(dx)\right)\int_{\Omega}f(y)d\nu_{\tau}(y)\log\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\right)\right]$
$\displaystyle=\mathbb{E}\left[\int_{\Omega}f(y)d\nu_{\tau}(y)\log\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\right)\right].$

Therefore,

$\displaystyle\frac{\mathbb{E}\left[\mathrm{Ent}_{\nu_{t}}[f]\right]}{\mathrm{Ent}_{\nu}[f]}$
$\displaystyle=\frac{\mathbb{E}\left[\int_{\Omega}f(x)\log
f(x)d\nu_{\tau}(x)\right]-\mathbb{E}\left[\int_{\Omega}f(y)d\nu_{\tau}(y)\log\left(\int_{\Omega}f(y)d\nu_{\tau}(y)\right)\right]}{\mathrm{Ent}_{\nu}[f]}$
$\displaystyle\leq\frac{\int_{\Omega}f(x)\log
f(x)d\nu(x)}{\mathrm{Ent}_{\nu}[f]}-\frac{\int_{\Omega}(Pf)(x)\log(Pf)(x)d\nu(x)}{\mathrm{Ent}_{\nu}[f]}$
$\displaystyle=1-\frac{\mathrm{Ent}_{\nu}[Pf]}{\mathrm{Ent}_{\nu}[f]}.$

Equation (11) follows by taking infimum over all $f:\Omega\to_{+}$.

##  3 Approximate conservation of variance and entropy

In this section we describe the main tools used to prove mixing bounds for the
dynamics associated with a localization scheme. We introduce the notions of
approximate conservation of variance and entropy which, in the context of the
coordinate-by-coordinate localization are related in a simple way to spectral
independence and entropic independence. In the context of stochastic
localization, the concept of variance decay has been applied in order to prove
a spectral gap for log-concave measures.

Here, we will see that the same underlying principle is relevant to both
techniques, and the difference is in the localization scheme being considered:
In both proof techniques, one of the main insights has to do with a connection
between the rate of variance decay and the covariance structure of a certain
class of measures. Thus our framework captures the relation between covariance
structures and variance / entropy decay in both settings using the same
derivation.

######  Definition 20.

(Approximate Conservation of Variance, discrete time). We say that a
localization process $(\nu_{i})_{i}$ satisfies
$(\kappa_{1},\kappa_{2},...)$-variance conservation up to time $t$, if for
every test function $\varphi:\Omega\to\mathbb{R}$ one has

$\mathbb{E}[\mathrm{Var}_{\nu_{i}}[\varphi]~{}~{}|~{}~{}\nu_{i-1}]\geq(1-\kappa_{i})\mathrm{Var}_{\nu_{i-1}}[\varphi],~{}~{}~{}\forall
1\leq i\leq t.$

The motivation behind this definition is given by the fact that

$\displaystyle\frac{\mathbb{E}[\mathrm{Var}_{\nu_{t}}[\varphi]]}{\mathrm{Var}_{\nu}[\varphi]}$
$\displaystyle=\mathbb{E}\left[\prod_{i=1}^{t}\frac{\mathrm{Var}_{\nu_{i}}[\varphi]}{\mathrm{Var}_{\nu_{i-1}}[\varphi]}\right]$
$\displaystyle=\mathbb{E}\left[\prod_{i=1}^{t}\mathbb{E}\left[\left.\frac{\mathrm{Var}_{\nu_{i}}[\varphi]}{\mathrm{Var}_{\nu_{i-1}}[\varphi]}\right|\nu_{i-1}\right]\right]\geq\prod_{i=1}^{t}(1-\kappa_{i}).$

In light of (10), we immediately obtain the following simple theorem which
relates between variance conservation and the spectral gap of the dynamics
associated with the localization process.

######  Proposition 21.

If the localization process $(\nu_{t})_{t}$ satisfies
$(\kappa_{1},\dots,\kappa_{t})$-approximate variance conservation then the
dynamics given equation (1) with $\tau=t$ has a spectral gap bounded below by
$\prod_{i=1}^{t}(1-\kappa_{i})$.

###  3.1 Approximate conservation of variance for linear-tilt localizations
and spectral independence

In this section we will present very simple derivation, which gives a powerful
tool for proving approximate variance conservation bounds for linear-tilt
localization schemes. A special case of this derivation will recover (in a
very simple way) the main theorem in the spectral independence framework of
[ALOG20].

Suppose that $\Omega\subset\mathbb{R}^{n}$. Suppose that $(\nu_{t})_{t}$ is a
localization process on $\Omega$ whose evolution is given by the equation

$\nu_{t+1}(x)=\nu_{t}(x)\left(1+\langle
x-\mathbf{b}(\nu_{t}),Z_{t}\rangle\right),~{}~{}\forall x\in\Omega,$ (12)

where $Z_{t}$ is a random vector satisfying $\mathbb{E}[Z_{t}|\nu_{t}]=0$.

Our first objective is to calculate the variance decay of a test function
along this process.

######  Claim 22.

For a test function $\varphi:\Omega\to\mathbb{R}$, we have

$\mathbb{E}\left[\left.\mathrm{Var}_{\nu_{t+1}}[\varphi]\right|\nu_{t}\right]-\mathrm{Var}_{\nu_{t}}[\varphi]=-\langle
v_{t},C_{t}v_{t}\rangle.$ (13)

where

$v_{t}:=\int_{\Omega}(x-\mathbf{b}(\nu_{t}))\varphi(x)\nu_{t}(dx)~{}~{}~{}\mbox{and}~{}~{}~{}C_{t}:=\operatorname{Cov}(Z_{t}|\nu_{t}).$

###### Proof.

Fix $\varphi:\Omega\to\mathbb{R}$. We calculate

$\displaystyle\mathbb{E}\left[\left.\mathrm{Var}_{\nu_{t+1}}[\varphi]\right|\nu_{t}\right]$
$\displaystyle=\mathbb{E}\left[\left.\int_{\Omega}\varphi(x)^{2}\nu_{t+1}(dx)\right|\nu_{t}\right]-\mathbb{E}\left[\left.\left(\int_{\Omega}\varphi(x)\nu_{t+1}(dx)\right)^{2}\right|\nu_{t}\right]$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\mathbb{E}_{\nu_{t}}[\varphi^{2}]-\mathbb{E}\left[\left.\left(\int_{\Omega}\left(1+\langle
x-\mathbf{b}(\nu_{t}),Z_{t}\rangle\right)\varphi(x)\nu_{t}(dx)\right)^{2}\right|\nu_{t}\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\mathbb{E}_{\nu_{t}}[\varphi^{2}]-\mathbb{E}_{\nu_{t}}[\varphi]^{2}-\mathbb{E}\left[\left.\left(\int_{\Omega}\langle
x-\mathbf{b}(\nu_{t}),Z_{t}\rangle\varphi(x)\nu_{t}(dx)\right)^{2}\right|\nu_{t}\right]$
$\displaystyle=\mathrm{Var}_{\nu_{t}}[\varphi]-\mathrm{Var}\left[\left.\left\langle\int_{\Omega}(x-\mathbf{b}(\nu_{t}))\varphi(x)\nu_{t}(dx),Z_{t}\right\rangle\right|\nu_{t}\right]$

where (i) uses (P2) and (ii) uses the fact that $\mathbb{E}[Z_{t}|\nu_{t}]=0$.
By definition of $C_{t}$ and $v_{t}$, the right-hand side is equal to
$\mathrm{Var}_{\nu_{t}}[\varphi]-\langle v_{t},C_{t}v_{t}\rangle$, which
completes the proof.

In order to establish an approximate variance conservation bound, we need to
give an upper bound on the expression $\langle v_{t},C_{t}v_{t}\rangle$. We
now arrive at what is perhaps the heart of the argument. We use the Cauchy-
Schwartz inequality, obtaining

$\displaystyle\langle v_{t},C_{t}v_{t}\rangle$
$\displaystyle=\left|\int_{\Omega}C_{t}^{1/2}(x-\mathbf{b}(\nu_{t}))\varphi(x)\nu_{t}(dx)\right|^{2}$
$\displaystyle=\sup_{|\theta|=1}\left(\int_{\Omega}\langle
C_{t}^{1/2}(x-\mathbf{b}(\nu_{t})),\theta\rangle\varphi(x)\nu_{t}(dx)\right)^{2}$
$\displaystyle\leq\sup_{|\theta|=1}\int_{\Omega}\langle
C_{t}^{1/2}(x-\mathbf{b}(\nu_{t})),\theta\rangle^{2}\nu_{t}(dx)\mathrm{Var}_{\nu_{t}}[\varphi]$
$\displaystyle=\|C_{t}^{1/2}\operatorname{Cov}(\nu_{t})C_{t}^{1/2}\|_{\mathrm{OP}}\mathrm{Var}_{\nu_{t}}[\varphi].$
(14)

Combining with (13) yields that

$\frac{\mathbb{E}\left[\left.\mathrm{Var}_{\nu_{t+1}}[\varphi]\right|\nu_{t}\right]}{\mathrm{Var}_{\nu_{t}}[\varphi]}\geq
1-\|C_{t}^{1/2}\operatorname{Cov}(\nu_{t})C_{t}^{1/2}\|_{\mathrm{OP}}.$ (15)

The derivation above is one of the key insights in the framework presented
here: A simple application of the Cauchy Schwartz inequality gives rise to the
role of the covariance structure in variance conservation.

Let us now examine how to apply (15) to the case of the coordinate-by-
coordinate localization. A simple calculation, using the definition (4) gives
that

$\displaystyle(n-t)\operatorname{Cov}[Z_{t}|\nu_{t}]_{i,i}$
$\displaystyle=\frac{1}{(1+\mathbf{b}(\nu_{t})_{i})^{2}}\frac{1+\mathbf{b}(\nu_{t})_{i}}{2}+\frac{1}{(1-\mathbf{b}(\nu_{t})_{i})^{2}}\frac{1-\mathbf{b}(\nu_{t})_{i}}{2}$
$\displaystyle=\frac{1}{1-\mathbf{b}(\nu_{t})_{i}^{2}}=(\operatorname{Cov}(\nu_{t})_{i,i})^{-1},$

where the last equality is a consequence of the fact that
$\int_{\Omega}x_{i}^{2}\nu_{t}(dx)=1$. Denoting $D_{t}$ to be the diagonal
matrix whose entries coincide with the diagonal entries of
$\operatorname{Cov}(\nu_{t})$, we finally have

$\|C_{t}^{1/2}\operatorname{Cov}(\nu_{t})C_{t}^{1/2}\|_{\mathrm{OP}}=\frac{1}{(n-t)}\|D_{t}^{-1/2}\operatorname{Cov}(\nu_{t})D_{t}^{-1/2}\|_{\mathrm{OP}}.$

Define for a measure $\tilde{\nu}$ on $\\{-1,1\\}^{n}$,

$\mathbf{Cor}(\tilde{\nu}):=\mathrm{diag}(\mathrm{Cov}(\tilde{\nu}))^{-1/2}\mathrm{Cov}(\tilde{\nu})\mathrm{diag}(\mathrm{Cov}(\tilde{\nu}))^{-1/2},$
(16)

where $\operatorname{diag}(\cdot)$ is the diagonal matrix obtained by setting
all the off-diagonal entries to $0$. So $\mathbf{Cor}(\tilde{\nu})$ is just
the matrix of correlations between different coordinates of $\tilde{\nu}$. We
will also consider the closely-related influence matrix of the measure,
defined as

$\mathbf{\Psi}(\nu)_{i,j}:=\mathbb{E}_{X\sim\nu}[X_{i}|X_{j}=1]-\mathbb{E}_{X\sim\nu}[X_{i}|X_{j}=-1].$
(17)

The following fact relates the correlation matrix and the influence matrix.
Its proof is postponed to Appendix A.

######  Fact 23.

We have
$\mathbf{\Psi}(\nu)=\operatorname{Cov}(\nu)\operatorname{diag}(\mathrm{Cov}(\nu))^{-1}$
and

$\|\mathbf{Cor}(\nu)\|_{\mathrm{OP}}=\rho(\mathbf{\Psi}(\nu))\leq\|\mathbf{\Psi}(\nu)\|_{\mathrm{OP}}.$
(18)

In light of the above fact, Equation (15) becomes

$\frac{\mathbb{E}\left[\left.\mathrm{Var}_{\nu_{t+1}}[\varphi]\right|\nu_{t}\right]}{\mathrm{Var}_{\nu_{t}}[\varphi]}\geq
1-\frac{1}{n-t}\rho(\mathbf{\Psi}(\nu_{t})).$

For $u\in\\{-1,0,1\\}^{n}$ define the $u$-pinning of a measure,
$\mathcal{R}_{u}\tilde{\nu}$ to be the restriction of $\tilde{\nu}$ to the
sub-cube $S_{u}$, where

$S_{u}:=\bigl{\\{}x\in\\{-1,1\\}^{n};~{}x_{i}u_{i}\geq 0,~{}\forall
i\in[n]\bigr{\\}}.$ (19)

Observe that under the coordinate-by-coordinate localization, $\nu_{t}$ is of
the form $\mathcal{R}_{u}\nu$ for some $u=u(t)$. The condition that
$\|\mathbf{\Psi}(\mathcal{R}_{u}\nu_{t})\|_{\mathrm{OP}}$ is bounded uniformly
in $u$ is called spectral independence. Plugging the above into (15) and
applying Proposition 21 recovers the main theorem in the spectral independence
framework [ALOG20]:

######  Theorem 24.

(A reformulation of [ALOG20, Theorem 1.3]) Suppose that $\nu$ is a measure on
$\\{-1,1\\}^{n}$ such that for all $u\in\\{-1,0,1\\}^{n}$,

$\rho(\mathbf{\Psi}(\mathcal{R}_{u}\nu))\leq\eta_{|u|_{1}}.$

Then the spectral gap of the $k$-Glauber dynamics on $\nu$ is at least
$\prod_{i=0}^{n-k-1}(1-\frac{\eta_{i}}{n-i})$.

######  Remark 25.

There are some delicate differences between the above theorem and [ALOG20,
Theorem 1.3]. In the latter, $\tilde{\eta}_{i}$ is taken to be the operator
norm of the matrix $\mathbf{\Psi}(\mathcal{R}_{i}\nu)-\mathbf{I}_{n}$ rather
than that of the matrix $\mathbf{\Psi}(\nu)$. Precisely, their result states
that spectral gap is bounded from below by the expression
$\frac{1}{n}\prod_{i=0}^{n-k-1}(1-\frac{\tilde{\eta}_{i}}{n-i-1})$ where
$\tilde{\eta}_{i}=\eta_{i}-1$. So the extra factor $1/n$ is traded for the
fact that $\eta_{i}$ can be replaced by $\tilde{\eta}_{i}=\eta_{i}-1$.

In our proof, we completely bypassed the need to use the notion of high-
dimensional expanders or the up-down walk. The inequalities relating different
levels of the up-down walk were replaced by a simple application of the
Cauchy-Schwartz inequality.

####  3.1.1 The case of stochastic localization; bounds for the spectral gap
of log-concave measures

The same derivation (almost verbatim) as above gives a similar bound for the
variance decay of the stochastic localization process (5). Here we briefly
outline the argument which can be found in [Eld].

Let $\nu_{t}$ be the stochastic localization process associated to a measure
$\nu$ on $\mathbb{R}^{n}$, via equation (5) with some driving matrix $C_{t}$.
Fix a test function $\varphi:\mathbb{R}^{n}\to\mathbb{R}$. The continuous
analogue of (13) takes the form

$d\mathrm{Var}_{\nu_{t}}[\varphi]=-\left|\int
C_{t}^{1/2}(x-\mathbf{b}(\nu_{t}))\varphi(x)d\nu_{t}(x)\right|dt+\mbox{martingale}.$

Equation (14) (or, in other words, an application of Cauchy Schwartz) gives

$\left|\int
C_{t}^{1/2}(x-\mathbf{b}(\nu_{t}))\varphi(x)d\nu_{t}(x)\right|\leq\|C_{t}^{1/2}\mathrm{Cov}(\nu_{t})C_{t}^{1/2}\|_{\mathrm{OP}}\mathrm{Var}_{\nu_{t}}[\varphi]$

which implies that

$d\mathrm{Var}_{\nu_{t}}[\varphi]\geq-\|C_{t}^{1/2}\mathrm{Cov}(\nu_{t})C_{t}^{1/2}\|_{\mathrm{OP}}\mathrm{Var}_{\nu_{t}}[\varphi]dt+\mbox{martingale}$

By integration, we get the variance decay bound

$\frac{\mathbb{E}[\mathrm{Var}_{\nu_{t}}[\varphi]]}{\mathrm{Var}_{\nu}[\varphi]}\geq\mathbb{E}\left[e^{\int_{0}^{t}\|C_{s}^{1/2}\mathrm{Cov}(\nu_{s})C_{s}^{1/2}\|_{\mathrm{OP}}ds}\right]^{-1}$
(20)

Therefore, upper bounds on the process
$t\to\|\mathrm{Cov}(\nu_{t})\|_{\mathrm{OP}}$ correspond to approximate
conservation of variance bounds.

A classical inequality by Brascamp and Lieb allows us to relate the Dirichlet
form $\mathbb{E}_{\nu}[|\nabla\varphi|^{2}]$ to
$\mathbb{E}[\mathrm{Var}_{\nu_{t}}[\varphi]]$. Namely, due to (6) we have that
the measure $\nu_{t}$ is $\alpha_{t}$-strongly log-concave with $\alpha_{t}$
being the smallest eigenvalue of $\Sigma_{t}=\int_{0}^{t}C_{s}^{2}ds$, which
implies that

$\mathbb{E}[\mathrm{Var}_{\nu_{t}}[\varphi]]\leq\frac{1}{\alpha_{t}}\mathbb{E}_{\nu}[|\nabla\varphi|^{2}].$

Combining this with (20) gives a way to obtain lower bounds for the spectral
gap of a measure $\nu$ on $\mathbb{R}^{n}$ via the analysis of the process
$t\to\|\mathrm{Cov}(\nu_{t})\|_{\mathrm{OP}}$. This is one of the main ideas
underlying the stochastic localization technique, which in particular led to
the near-solution, due to the first author ([Che21]), of the Kannan-Lovász-
Simonovits conjecture ([KLS95a]) and Bourgain’s slicing problem.

###  3.2 Approximate conservation of entropy

It turns out that there are also natural sufficient conditions regarding the
conservation of the entropy along a localization process. These conditions are
closely related to the notion of entropic independence put forth in [AJK+21b].

######  Definition 26.

(Entropy conservation, discrete time). We say that a localization process
$(\nu_{i})_{i}$ satisfies $(\kappa_{1},\kappa_{2},...)$-entropy conservation
up to time $t$, if for every test function $f:\Omega\to\mathbb{R}_{+}$ one has

$\mathbb{E}[\mathrm{Ent}_{\nu_{i}}[f]~{}~{}|~{}~{}\nu_{i-1}]\geq(1-\kappa_{i})\mathrm{Ent}_{\nu_{i-1}}[f],~{}~{}~{}\forall
1\leq i\leq t.$

A telescopic-product argument, completely analogous to the one in the proof of
Proposition 21, together with equation (11), yields the following.

######  Proposition 27.

If the localization process $(\nu_{t})_{t}$ satisfies a
$(\kappa_{1},\dots,\kappa_{t})$-entropy conservation then the dynamics given
equation (1) with $\tau=t$ has a MLSI coefficient bounded below by
$\prod_{i=1}^{t}(1-\kappa_{i})$.

######  Remark 28.

We refer the reader to [AJK+21b, Section 1.1] for some examples where this
bound can be applied. Usually, however, the expression
$\prod_{i=1}^{t}(1-\kappa_{i})$ will give optimal bounds. Below we will see
better ways to extracting the power of approximate conservation of entropy.

####  3.2.1 Entropic stability

Next, we discuss the case $\Omega\subset\mathbb{R}^{n}$ (relevant in
particular to $\Omega=\mathbb{R}^{n}$ and $\Omega=\\{-1,1\\}^{n}$). We
introduce a notion which turns out to be very useful in controlling the decay
of entropy along linear-tilt localizations.

For a measure $\nu$ on $\mathbb{R}^{n}$ and $v\in\mathbb{R}^{n}$, define the
exponential tilt $\mathcal{T}_{v}\nu$ by

$\frac{d\mathcal{T}_{v}\nu(x)}{d\nu(x)}:=\frac{e^{\langle v,x\rangle}}{\int
e^{\langle v,z\rangle}d\nu(z)}.$

A central definition in our framework is the following.

######  Definition 29.

(Entropic stability). For $\nu$ on $\Omega\subset\mathbb{R}^{n}$, a function
$\psi:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R}_{+}$ and $\alpha>0$, we
say that $\nu$ is $\alpha$-entropically stable with respect to $\psi$ if

$\psi(\mathbf{b}(\mathcal{T}_{v}\nu),\mathbf{b}(\nu))\leq\alpha\mathrm{D_{KL}}(\mathcal{T}_{v}\nu||\nu),~{}~{}\forall
v\in\mathbb{R}^{n}.$

In order for the definition to make sense, $\psi(x,y)$ needs to vanish when
$x=y$. For the sake of intuition, we may think of the case
$\psi(x,y)=|x-y|^{2}$. Roughly speaking, entropic stability amounts to the
fact that the center of mass does not move much when tilting the measure in
terms of the relative entropy of the tilt.

What follows is a very useful observation, based the principle of maximum
entropy. This observation is essentially due to [AJK+21b], where it was used
in the context of entropic independence, which can be understood as a specific
case of entropic stability.

######  Fact 30.

For every measure $\nu$ on $\Omega$ and every function
$g:\mathbb{R}^{n}\to\mathbb{R}$, one has

$\inf_{\mu}\frac{\mathrm{D_{KL}}(\mu||\nu)}{g(\mathbf{b}(\mu))}=\inf_{v\in\mathbb{R}^{n}}\frac{\mathrm{D_{KL}}(\mathcal{T}_{v}\nu||\nu)}{g(\mathbf{b}(\mathcal{T}_{v}\nu))}.$
(21)

###### Proof.

By the maximum entropy principle, the minimum over measures $\mu$ of the
relative entropy $\mathrm{D_{KL}}(\mu||\nu)$ under the linear constraint
$\mathbf{b}(\mu)=b_{0}$ is attained for a measure such that
$\frac{d\mu}{d\nu}\propto\exp(L(\cdot))$ for some linear function
$L:\mathbb{R}^{n}\to\mathbb{R}$, or in other words the optimal $\mu$ is of the
form $\mathcal{T}_{v}\nu$ for some $v\in\mathbb{R}^{n}$.

An immediate corollary is the following,

######  Lemma 31.

Suppose that a measure $\nu$ is $\alpha$-entropically stable with respect to
$\psi$. Then, for every measure $\mu$ which is absolutely continuous with
respect to $\nu$, we have

$\psi(\mathbf{b}(\mu),\mathbf{b}(\nu))\leq\alpha\mathrm{D_{KL}}(\mu||\nu).$

######  Remark 32.

In view of the last lemma, we see that the notion of entropic stability is
closely related to transportation-entropy bounds introduced by Talagrand (see
[GL10] for a survey). While entropic stability refers to the fact that the
center of mass does not move under change of measure with small relative
entropy, a transportation-entropy inequality alludes to the transportation
distance being small under such change of measure. Thus, in a sense entropic
stability bounds are a weaker version of transportation-entropy bounds.

One last ingredient which will be useful to us is the following formula which
can be obtained via the logarithmic Laplace transform.

######  Lemma 33.

([BE19, Lemma 1]). Let $\nu$ be a measure on $\mathbb{R}^{n}$ such that
$\mathrm{Cov}(\nu)$ is invertible. Denote by $K\subset\mathbb{R}^{n}$ the
interior of the convex hull of the support of $\nu$. Then there exists a
unique function $v:K\to\mathbb{R}^{n}$ such that

$\mathbf{b}(\mathcal{T}_{v(x)}\nu)=x,~{}~{}\forall x\in K.$

Moreover, denoting $g(x):=\mathrm{D_{KL}}(\mathcal{T}_{v(x)}\nu||\nu)$, we
have

$\nabla
g(\mathbf{b}(\nu))=0,~{}~{}~{}\nabla^{2}g(x)=\mathrm{Cov}(\mathcal{T}_{v(x)}\nu)^{-1},~{}~{}\forall
x\in K.$ (22)

Finally, if $L_{\nu}(\theta):=\log\int e^{\langle x,\theta\rangle}d\nu(x)$ is
the Logarithmic Laplace transform of $\nu$, then we have that

$g(x)=\sup_{\theta\in\mathbb{R}^{n}}\langle x,\theta\rangle-L_{\nu}(\theta)$

hence $g$ is the Legendre dual of $L_{\nu}$.

######  Remark 34.

The role of the logarithmic Laplace transform in concentration inequalities on
the discrete hypercube was suggested in [ES22]. The boundedness of its hessian
is closely related to the notion of fractional log-concavity of the
characteristic polynomial, introduced in [AASV21].

####  3.2.2 The case of the coordinate-by-coordinate localization: Entropic
independence

As a warm-up, in this section we essentially recover the results of [AJK+21b],
deriving a natural criterion for approximate conservation of entropy for
$\Omega=\\{-1,1\\}^{n}$ with the coordinate-by-coordinate localization
process. The proof here boils down to ideas which are quite similar to the
ones that appear in [AJK+21b], with two crucial differences which will
(arguably) make our argument cleaner: 1. We directly analyze measures on the
hypercube rather than measures on $\binom{n}{k}$. 2. The notion of _fractional
log-concavity_ is replaced by a definition which involves the logarithmic
Laplace transform of the measure, which seems to arise naturally in this
context, and due to which the proof involves much simpler formulas.

For $x,y\in[-1,1]^{n}$, define

$H(x,y)=\sum_{i=1}^{n}\mathbf{1}_{|y_{i}|<1}\left(\frac{1+x_{i}}{2}\log\left(\frac{1+x_{i}}{1+y_{i}}\right)+\frac{1-x_{i}}{2}\log\left(\frac{1-x_{i}}{1-y_{i}}\right)\right),$
(23)

It turns out that in the context of the coordinate-by-coordinate scheme, the
key will be to consider $\alpha$-entropic stability with respect to the
function $\psi(x,y)=H(x,y)$. With this choice, entropic stability is
essentially the same is entropic independence introduced in [AJK+21b], and the
following proposition shows that it implies approximate conservation of
entropy under the coordinate-by-coordinate localization.

######  Proposition 35.

Let $\nu_{t}$ be the coordinate-by-coordinate localization process for some
measure $\nu$ on $\\{-1,1\\}^{n}$. For every $t$, if the measure $\nu_{t}$ is
$\kappa$-entropically stable with respect to the function $\psi(x,y)=H(x,y)$
then we have the approximate conservation of entropy bound

$\mathbb{E}\left[\mathrm{Ent}_{\nu_{t+1}}[f]~{}|\nu_{t}\right]\geq\left(1-\frac{\kappa}{n-t}\right)\mathrm{Ent}_{\nu_{t}}[f],$

for all $f:\Omega\to\mathbb{R}_{+}$ and $t\in[n-1]$. Consequently, if
$\mathcal{R}_{u}\nu$ is $\kappa$-entropically stable with respect to the same
function, for all $u\in\\{-1,0,1\\}^{n}$, then the $\ell$-Glauber dynamics
$P=P^{\mathrm{GD},\ell}(\nu)$ has MLSI coefficient

$\mathrm{\rho_{LS}}\left(P\right)\geq\prod_{i=0}^{n-\ell-1}\left(1-\frac{\kappa}{n-i}\right).$

###### Proof.

Fix a probability measure $\nu$ on $\Omega$ and a function
$f:\Omega\to\mathbb{R}_{+}$. Let $(\nu_{t})_{t}$ be the coordinate-by-
coordinate localization process of $\nu$. The derivation obtained in
Subsection 2.4.1 gives the following: Conditioned on $\nu_{t}$, we have

$\displaystyle\int f(x)d\nu_{t+1}(x)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:cbctilt}}}{{=}}\int
f(x)\left(1+\langle x-\mathbf{b}(\nu_{t}),Z\rangle\right)d\nu_{t}(x)$
$\displaystyle=\int f(x)d\nu_{t}(x)\left(1+\left\langle\left(\frac{\int
xf(x)d\nu_{t}(x)}{\int
f(x)\nu_{t}(dx)}-\mathbf{b}(\nu_{t})\right),Z\right\rangle\right)$
$\displaystyle=\nu_{t}(f)\left(1+\langle V,Z\rangle\right)$ (24)

where

$V:=\frac{\int xf(x)\nu_{t}(dx)}{\int f(x)\nu_{t}(dx)}-\mathbf{b}(\nu_{t})$

and

$Z=\mathbf{e}_{k_{t+1}}\times\begin{cases}\frac{1}{1+\mathbf{b}(\nu_{t})_{k_{t+1}}}&\mbox{with
probability}~{}~{}\frac{1+\mathbf{b}(\nu_{t})_{k_{t+1}}}{2},\\\
\frac{-1}{1-\mathbf{b}(\nu_{t})_{k_{t+1}}}&\mbox{with
probability}~{}~{}\frac{1-\mathbf{b}(\nu_{t})_{k_{t+1}}}{2}.\end{cases}$

We have

$\displaystyle\mathbb{E}\left[(1+\langle V,Z\rangle)\log(1+\langle
V,Z\rangle)|\nu_{t}\right]=$
$\displaystyle\frac{1}{n-t}\sum_{i\in[n]\setminus\\{k_{1},\dots,k_{t}\\}}q(t;i)$

where

$q(t;i)=\mathbb{E}\left[(1+\langle V,Z\rangle)\log(1+\langle
V,Z\rangle)|\nu_{t},k_{t+1}=i\right].$

Now, writing $\frac{d\mu_{t}}{d\nu_{t}}(x)=\frac{f(x)}{\int f(z)d\nu_{t}(z)}$,
we have $V=\mathbf{b}(\mu_{t})-\mathbf{b}(\nu_{t})$ and

$\displaystyle q(t;i)$
$\displaystyle=\frac{1+b(\nu_{t})_{i}}{2}\left(1+\frac{V_{i}}{1+\mathbf{b}(\nu_{t})_{i}}\right)\log\left(1+\frac{V_{i}}{1+\mathbf{b}(\nu_{t})_{i}}\right)$
$\displaystyle~{}~{}~{}~{}+\frac{1-b(\nu_{t})_{i}}{2}\left(1-\frac{V_{i}}{1-\mathbf{b}(\nu_{t})_{i}}\right)\log\left(1-\frac{V_{i}}{1-\mathbf{b}(\nu_{t})_{i}}\right)$
$\displaystyle=\frac{1+\mathbf{b}(\mu_{t})_{i}}{2}\log\left(\frac{1+\mathbf{b}(\mu_{t})_{i}}{1+\mathbf{b}(\nu_{t})_{i}}\right)+\frac{1-\mathbf{b}(\mu_{t})_{i}}{2}\log\left(\frac{1-\mathbf{b}(\mu_{t})_{i}}{1-\mathbf{b}(\nu_{t})_{i}}\right).$

Combining the last three displays, we have

$\mathbb{E}\left[(1+\langle V,Z\rangle)\log(1+\langle
V,Z\rangle)|\nu_{t}\right]=\frac{1}{n-t}H(\mathbf{b}(\mu_{t}),\mathbf{b}(\nu_{t})).$
(25)

We finally get

$\mathbb{E}[\left.\mathrm{Ent}_{\nu_{t+1}}[f]\right|~{}\nu_{t}]=\mathrm{Ent}_{\nu_{t}}[f]-\frac{1}{n-t}\nu_{t}(f)H(\mathbf{b}(\mu_{t}),\mathbf{b}(\nu_{t})).$

The assumption that $\nu_{t}$ is $\kappa$-entropically stable with respect to
$h$, combined with Lemma 31, amounts to

$H(\mathbf{b}(\mu_{t}),\mathbf{b}(\nu_{t}))\leq\kappa\mathrm{D_{KL}}(\mu||\nu)=\frac{\kappa}{\nu_{t}(f)}\mathrm{Ent}_{\nu_{t}}[f].$

Combining the last two displays gives

$\mathbb{E}\left[\left.\mathrm{Ent}_{\nu_{t+1}}[f]\right|\nu_{t}\right]\geq\mathrm{Ent}_{\nu_{t}}[f]-\frac{\kappa}{n-t}\mathrm{Ent}_{\nu_{t}}[f],$

By definition of approximate entropy conservation, this completes the proof of
the first part. The second part follows immediately by the use of Proposition
27.

In the paper [AJK+21b], the authors show that entropic independence is
naturally related to the log-concavity of a power of the characteristic
polynomial, referred to as _fractional log-concavity_. Next, we show that a
somewhat analogous, very simple derivation, gives that entropic stability with
respect to the function $h$ is implied by the fact that exponential tilts of
the measure have a bounded correlation matrix. The proof of the next lemma is
found in Appendix A

######  Lemma 36.

Suppose that a measure $\nu$ on $\\{-1,1\\}^{n}$ satisfies

$\|\mathbf{Cor}(\mathcal{T}_{v}\nu)\|_{\mathrm{OP}}\leq\alpha,~{}~{}\forall
v\in\mathbb{R}^{n}$ (26)

where $\mathbf{Cor}(\cdot)$ is defined in (16). In this case, $\nu$ is
$\alpha$-entropically stable with respect to $\psi(x,y)=H(x,y)$.

######  Remark 37.

Fact 23 shows that $\alpha$-spectral independence is equivalent to the fact
that $\mathrm{Cov}(\nu)\preceq(\alpha+1)~{}\mathrm{diag}(\mathrm{Cov}(\nu))$.
Therefore, the condition given in the lemma can be thought of as spectral
independence for all tilts.

######  Remark 38.

The condition (26) is the exact condition given in [ES22], where it is shown
that it implies nontrivial concentration of Lipchitz functions.

####  3.2.3 Entropic decay for stochastic localization

Let $\nu$ be a measure on $\mathbb{R}^{n}$ and consider the stochastic
localization process $(\nu_{t})_{t}$ defined by (5). Fix a non-zero,
measurable function $f:\Omega\to\mathbb{R}_{+}$. For every $t>0$, define a
probability measure $\mu_{t}$ by the equation

$\frac{d\mu_{t}}{d\nu_{t}}(x)=\frac{f(x)}{\int f(x)\nu_{t}(dx)}.$

Consider the martingale

$M_{t}:=\nu_{t}(f)=\int f(x)F_{t}(x)\nu(dx).$

Using equation (5), we can calculate

$\displaystyle dM_{t}$ $\displaystyle=\int f(x)F_{t}(x)\langle
x-\mathbf{b}(\nu_{t}),C_{t}dB_{t}\rangle\nu(dx)$
$\displaystyle=M_{t}\bigl{\langle}C_{t}(\mathbf{b}(\mu_{t})-\mathbf{b}(\nu_{t})),dB_{t}\bigr{\rangle}.$

Using Itô’s formula, we have

$\displaystyle d(M_{t}\log M_{t})$
$\displaystyle=\frac{d[M]_{t}}{2M_{t}}+\mbox{ martingale}$
$\displaystyle=\frac{1}{2}M_{t}|C_{t}(\mathbf{b}(\mu_{t})-\mathbf{b}(\nu_{t}))|^{2}dt+\mbox{
martingale}.$

We finally obtain

$\displaystyle d\mathrm{Ent}_{\nu_{t}}[f]$ $\displaystyle=d\int f(x)\log
f(x)\nu_{t}(dx)-d(M_{t}\log M_{t})$
$\displaystyle=-\frac{1}{2}\nu_{t}(f)\left|C_{t}\left(\mathbf{b}(\mu_{t})-\mathbf{b}(\nu_{t})\right)\right|^{2}dt+\mbox{martingale}.$
(27)

We arrive at the following,

######  Proposition 39.

For a fixed $T>0$, suppose that, almost surely for all $t\in[0,T]$ that
$\nu_{t}$ is $\alpha_{t}$-entropically stable with respect to the function
$\psi(x,y)=\frac{1}{2}|C_{t}(x-y)|^{2}$. Then we have the approximate entropic
conservation bound

$\mathbb{E}\left[\mathrm{Ent}_{\nu_{T}}[f]\right]\geq
e^{-\int_{0}^{T}\alpha_{t}dt}\mathrm{Ent}_{\nu}[f].$ (28)

###### Proof.

The entropic stability assumption combined with Lemma 31 and equation (27)
yields that

$d\mathrm{Ent}_{\nu_{t}}[f]\geq-\alpha_{t}\mathrm{Ent}_{\nu_{t}}[f]dt+\mbox{martingale},~{}~{}\forall
t\in[0,T].$

Consequently, by applying Ito’s formula, we have that the process $t\to
e^{\int_{0}^{t}\alpha_{s}ds}\mathrm{Ent}_{\nu_{t}}[f]$ is a submartingale.
Therefore,

$\mathbb{E}\left[e^{\int_{0}^{T}\alpha_{t}dt}\mathrm{Ent}_{\nu_{T}}[f]\right]\geq\mathrm{Ent}_{\nu}[f],$

which completes the proof.

The following lemma is useful for establishing entropic stability with respect
to quadratic functions.

######  Lemma 40.

Let $\nu$ be a measure on $\mathbb{R}^{n}$ and $C,A$ be positive-definite
matrices. Suppose that for every $v\in\mathbb{R}^{n}$ one has

$\mathrm{Cov}(\mathcal{T}_{v}\nu)\preceq A,$ (29)

Then $\nu$ is $\alpha$-entropically stable with respect to the function
$\psi(x,y)=\frac{1}{2}|C(x-y)|^{2}$, for $\alpha=\|CAC\|_{\mathrm{OP}}$.

###### Proof.

Define $v(x)$, $g(x):=\mathrm{D_{KL}}(\mathcal{T}_{v(x)}\nu||\nu)$ and $K$ as
in Lemma 33. We have,

$\nabla^{2}g(x)\stackrel{{\scriptstyle\eqref{eq:denttilt}}}{{=}}\mathrm{Cov}(\mathcal{T}_{v(x)}\nu)^{-1}\stackrel{{\scriptstyle\eqref{eq:entstabtilt}}}{{\succeq}}A^{-1},~{}~{}\forall
x\in K,$

and $\nabla g(\mathbf{b}(\nu))=0$. Define
$h(x)=\frac{1}{2}|C(x-\mathbf{b}(\nu))|^{2}$. Then $\nabla
h(\mathbf{b}(\nu))=0$ and, for all $x$, $\nabla^{2}h(x)=C^{2}$. Therefore, for
all $x\in K$, we have

$\|CAC\|_{\mathrm{OP}}\nabla^{2}g(x)\succeq\|CAC\|_{\mathrm{OP}}A^{-1}\succeq
C^{2}=\nabla^{2}h(x).$

Since $g(\mathbf{b}(\nu))=h(\mathbf{b}(\nu))=0$ and $\nabla
g(\mathbf{b}(\nu))=\nabla h(\mathbf{b}(\nu))=0$, $g$ and $h$ coincide up to
first order Taylor expansion around $\mathbf{b}(\nu)$. It follows that
$\|CAC\|_{\mathrm{OP}}g(x)\geq h(x)$. Together with Fact 30, we complete the
proof.

####  3.2.4 Entropic decay for the negative-fields localization

It turns out that the entropy decay for the negative-fields localization is
also governed by the function $H(x,y)$ in equation (23).

######  Proposition 41.

Consider a localization process $\nu_{t}$ obtained via the negative-fields
localization scheme (with the choice $v(t)=-t\vec{\mathbf{1}}$). Let
$f:\\{-1,1\\}^{n}\to\mathbb{R}$ and let $\mu_{t}$ be the measure obtained via
the formula $\frac{d\mu_{t}(x)}{d\nu_{t}(x)}=f(x)$. Suppose that $\nu_{t}$ is
$\alpha$-entropically stable with respect to the function $H(x,y)$ defined in
equation (23), then we have the approximate entropy conservation bound

$\mathbb{E}[\mathrm{Ent}_{\nu_{t+h}}[f]|\nu_{t}]\geq\mathrm{Ent}_{\nu_{t}}[f](1-4h\alpha)+o(h),~{}~{}~{}\forall
t,h\geq 0.$

The proof of the above proposition is just a calculation, in the same spirit
as the derivation of entropic decay for the coordinate-by-coordinate process
and stochastic localization. The proof is found in Appendix A.

###  3.3 Entropic stability via spectral independence

Lemma 36 and Lemma 40 both rely on the logarithmic Laplace transform to show
that entropic-stability can be deduced from bounds on the covariance matrix of
different tilts of the measure. On the other hand, the weaker notion of
spectral independence only requires a corresponding bound on the covariance
matrix itself, and in order to get a spectral gap via the spectral
independence framework, we need a bound on the influence matrix for all
pinnings rather than all tilts (see remark 37).

It turns out that requiring all pinnings of a measure $\nu$ to be spectrally-
independent is sufficient for entropic stability with respect to a quadratic
function. Recall the definition of $\mathbf{\Psi}(\nu)$ from equation (16) and
recall that for all $u\in\\{-1,0,1\\}^{n}$, $\mathcal{R}_{u}\nu$ is defined to
be the restriction of $\nu$ to the subcube $S_{u}$ (defined in (19)).

######  Theorem 42.

Let $\nu$ be a probability measure on $\\{-1,1\\}^{n}$ and let $\alpha\geq 1$.
Suppose that

$\displaystyle\left\|\mathbf{Cor}(\mathcal{R}_{u}\nu)\right\|_{\mathrm{OP}}\leq\alpha,~{}~{}~{}\forall
u\in\left\\{-1,0,1\right\\}^{n}.$ (30)

Then $\nu$ is $8\alpha$-entropically stable with respect to
$\psi(x,y)=\frac{1}{2}|x-y|^{2}$.
Furthermore, if for some constants $K\geq 1,C\geq 1$, for every $i\in[n]$ and
for every $u,w\in\\{-1,0,1\\}^{n}$ with
$\text{supp}(u)\cap\text{supp}(w)=\emptyset$ with $u_{i}=w_{i}=0$, we have

$\displaystyle\frac{1+\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{u}\nu)}{1-\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{u}\nu)}$
$\displaystyle\leq
K\frac{1+\mathbf{b}_{i}(\mathcal{R}_{u}\nu)}{1-\mathbf{b}_{i}(\mathcal{R}_{u}\nu)},\text{
and }$ (31) $\displaystyle 1-\mathbf{b}_{i}(\mathcal{R}_{u}\nu)$
$\displaystyle\geq\frac{1}{C},$ (32)

then $\nu$ is $768\alpha K^{3}C$-entropically stable with respect to the
function $H(x,y)$ as defined in equation (23).

The proof is found in Section 6.

Recall the $\ell$-Glauber dynamics (see remark 12 above), which is associated
to the coordinate-by-coordinate localization scheme with stopping time
$\tau=n-\ell$. Denote its transition kernel by $P^{\ell-\mathrm{GD}}(\nu)$.

The above theorem will allow us to recover the extension of the spectral
independence framework due to Chen, Liu and Vigoda ([CLV21]), and show that
spectral independence for all pinnings implies an MLSI for the $\ell$-Glauber
dynamics with $\ell=\Omega(n)$. This is true under the extra condition that
the marginals of the measure are bounded away from $-1$ and $1$ under
pinnings:

######  Definition 43.

(bounded marginals). We say that a measure $\nu$ on $\mathbb{R}^{n}$ has
$b$-marginally bounded if for all $i\in[n]$ and all $u\in\\{-1,0,1\\}^{n}$
with $u_{i}=0$, we have

$|\mathbf{b}(\mathcal{R}_{u}\nu)_{i}|\leq 1-b.$

The following theorem essentially recovers the framework of [CLV21].

######  Theorem 44.

Let $\nu$ be a probability measure on $\\{-1,1\\}^{n}$ and let $\alpha\geq 1$.
Suppose that

$\rho(\mathbf{\Psi}(\mathcal{R}_{u}\nu))\leq\alpha,~{}~{}~{}\forall
u\in\\{-1,0,1\\}^{n}.$ (33)

Moreover, suppose that $\nu$ is $b$-marginally bounded. Then for every
$\varepsilon\in\left(\frac{8a}{bn},\frac{1}{2}\right)$,

$\mathrm{\rho_{LS}}(P^{\ell-\mathrm{GD}})(\nu)\geq\varepsilon^{C\alpha/b}.$

where $\ell=\lceil\varepsilon n\rceil$ and $C>0$ is a universal constant.

######  Remark 45.

This result also holds under a weaker condition than having bounded-marginals,
namely it is enough that the measure has $(1/b)$-tame marginals, see
definition 59 below.

In [CLV21], a clever argument is used to show that when the model has bounded
degrees (see [CLV21] for a precise definition) and $\varepsilon$ is a small
enough constant (as a function of the maximum degree), then mixing of the
$\ell$-Glauber dynamics for $\ell=\varepsilon n$ implies mixing of the
$1$-Glauber dynamics. In fact, it is even easier to show that in the case of
bounded degrees, one may sample directly by using the $\ell$-Glauber dynamics,
as the single step has complexity bounded by $n^{o(1)}$.

###### Proof of Theorem 44.

The bounded marginals assumption implies that the condition (31) holds true
for any pinning of the measure $\nu$ with $K=2/b$. Using Theorem 42, we have
that for every $u\in\\{-1,0,1\\}^{n}$, $\mathcal{R}_{u}\nu$ is
$(48\alpha/b)$-entropically stable with respect to $H(x,y)$ defined in (23).
An application of Proposition 35 gives that the $\ell$-Glauber dynamics has
MLSI

$\displaystyle\mathrm{\rho_{LS}}(P^{\ell-\mathrm{GD}})(\nu)$
$\displaystyle\geq\prod_{i=0}^{n-\ell-1}\left(1-\frac{48\alpha
b^{-1}}{n-i}\right)$
$\displaystyle=\exp\left(\sum_{i=0}^{\lceil(1-\varepsilon)n\rceil}\log\left(1-\frac{100\alpha
b^{-1}}{n-i}\right)\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}\exp\left(-\sum_{i=0}^{\lceil(1-\varepsilon)n\rceil}\frac{200\alpha
b^{-1}}{n-i}\right)\geq\varepsilon^{Ca/b},$

where (i) uses the assumption that $\varepsilon>\frac{8a}{bn}$ and the fact
that $\log(1-x)\geq-2x$ for $x>-1/2$. This completes the proof.

##  4 Annealing via a localization scheme

A powerful tool in our framework will be to conceptually concatenate two
localization schemes, running one localization scheme up to some time $t$ and
then running a second scheme where $\nu_{t}$ is used as the initial condition.
As we will see, in many cases this tool will allow us to use the first stage
as an annealing procedure which tames the measure in a way that provides a
good starting point for the second stage.

Consider two localization schemes $\mathcal{L}_{i},\mathcal{L}_{f}$ on a space
$\Omega$. Let $\nu$ be a measure on $\Omega$ and consider localization the
process $\left(\nu^{(i)}_{t}\right)_{t}$ obtained from applying
$\mathcal{L}_{i}$ to $\nu$. Let $\mathfrak{a}$ be a stopping time adapted to
the filtration of this process. Now, conditional on
$\nu^{(i)}_{\mathfrak{a}}$, let $\left(\nu^{(f)}_{t}\right)_{t}$ be a
localization process obtained from applying $\mathcal{L}_{f}$ to
$\nu^{(i)}_{\mathfrak{a}}$. We may obtain a localization process
$(\nu_{t})_{t}$ by defining

$\nu_{t}:=\begin{cases}\nu^{(i)}_{t}&t\leq\mathfrak{a}\\\
\nu^{(f)}_{t-\tau}&t\geq\mathfrak{a}.\end{cases}$

We denote the localization scheme mapping $\nu$ to $(\nu_{t})_{t}$ by
$\mathrm{concat}(\mathcal{L}_{i},\mathcal{L}_{f},\mathfrak{a})$.

The advantage of concatenating two localization schemes is demonstrated by the
following theorem.

######  Theorem 46.

(Annealing - variance). Let $\mathcal{L}_{i},\mathcal{L}_{f}$ be two
localization schemes on $\Omega$ such that the latter is a Doob localization
scheme. Let $\nu$ be a probability measure to which we assign a localization
process $(\nu_{t})_{t}$ from
$\mathrm{concat}(\mathcal{L}_{i},\mathcal{L}_{f},\mathfrak{a})$ for a stopping
time $\mathfrak{a}$. Fix $\tau>0$ and let
$P=P^{(\mathcal{L}_{f},\tau)}(\nu_{\mathfrak{a}})$ be the (random) transition
kernel associated to $\nu_{\mathfrak{a}}$ via $(\mathcal{L}_{f},T)$ using (1).
Suppose that,

  1. 1.

We have the approximate variance conservation bound

$\frac{\mathbb{E}\left[\mathrm{Var}_{\nu_{\mathfrak{a}}}[\varphi]\right]}{\mathrm{Var}_{\nu}[\varphi]}\geq\varepsilon,~{}~{}\forall\varphi:\Omega\to\mathbb{R}.$

  2. 2.

Almost-surely, we have

$\mathfrak{gap}(P(\nu_{\mathfrak{a}}))\geq\delta.$

Under these two assumptions, we have that the Markov chain associated to $\nu$
via $\mathcal{L}_{f}$ has spectral gap at least $\varepsilon\delta$.

In the above theorem, the localization scheme $\mathcal{L}_{i}$ is thought of
as an annealing procedure which takes a (potentially not well-behaved) measure
$\nu$, and outputs a measure $\nu_{\mathfrak{a}}$ which is well-behaved in the
sense of assumption 2. Assumption 1 tells us that we did not lose much of the
variance throughout the annealing process. The proof relies on the fact that
the Dirichlet form associated by a Doob localization is a supermartingale -
this fact was crucially used in [EKZ21] in the context of stochastic
localization.

Next, we have a completely analogous theorem for the entropy.

######  Theorem 47.

(Annealing - entropy). Let $\mathcal{L}_{i},\mathcal{L}_{f}$ be two
localization schemes on $\Omega$ such that the latter is a Doob localization
scheme. Let $\nu$ be a probability measure to which we assign a localization
process $(\nu_{t})_{t}$ from
$\mathrm{concat}(\mathcal{L}_{i},\mathcal{L}_{f},\mathfrak{a})$ for a stopping
time $\mathfrak{a}$. Fix $\tau>0$ and let
$P=P^{(\mathcal{L}_{f},\tau)}(\nu_{\mathfrak{a}})$ be the (random) transition
kernel associated to $\nu_{\mathfrak{a}}$ via $(\mathcal{L}_{f},T)$ using (1).
Suppose that,

  1. 1.

We have the entropy conservation inequality

$\frac{\mathbb{E}\left[\mathrm{Ent}_{\nu_{\mathfrak{a}}}[f]\right]}{\mathrm{Ent}_{\nu}[f]}\geq\varepsilon,~{}~{}\forall
f:\Omega\to\mathbb{R}_{+}.$

  2. 2.

Almost-surely, one has

$\mathrm{\rho_{LS}}(P(\nu_{\mathfrak{a}}))\geq\delta.$ (34)

Under these two assumptions, we have that the Markov chain associated to $\nu$
via $\mathcal{L}_{f}$ has an MLSI coefficient of at least $\varepsilon\delta$.

Let $P^{(t)}=P^{(\mathcal{L}_{f},\tau)}(\nu_{t})$. Our main step towards
proving the two theorems is the following.

######  Proposition 48.

For every $\varphi:\Omega\to\mathbb{R}$ and $f:\Omega\to\mathbb{R}_{+}$, the
processes

$t\to\int_{\Omega\times\Omega}\varphi(x)\varphi(y)dP^{(t)}_{x}(y)d\nu^{(i)}_{t}(x)$

and

$t\to\int_{\Omega}P^{(t)}f(x)\log P^{(t)}f(x)d\nu^{(i)}_{t}(x)$

are submartingales.

The proof of Proposition 48 is deferred to Appendix A.1. Let us see how
theorems 46 and 47 follow from this proposition.

###### Proof of Theorem 46.

We write

$\displaystyle\quad\frac{1}{2}\int_{\Omega}\int_{\Omega}\left(\varphi(x)-\varphi(y)\right)^{2}dP^{(0)}_{x}(y)d\nu(x)$
$\displaystyle=\int_{\Omega}\varphi(x)^{2}d\nu(x)-\int_{\Omega}\int_{\Omega}\varphi(x)\varphi(y)dP^{(0)}_{x}(y)d\nu(x)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}\mathbb{E}\left[\int_{\Omega}\varphi(x)^{2}d\nu^{(i)}_{\mathfrak{a}}(x)-\int_{\Omega}\int_{\Omega}\varphi(x)\varphi(y)dP^{(\mathfrak{a})}_{x}(y)d\nu(x)\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{2}\int_{\Omega}\int_{\Omega}\left(\varphi(x)-\varphi(y)\right)^{2}dP^{(\mathfrak{a})}_{x}(y)d\nu^{(i)}_{\mathfrak{a}}(x)\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\geq}}\delta\mathbb{E}\left[\mathrm{Var}_{\nu^{(i)}_{\mathfrak{a}}}[\varphi]\right]$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\geq}}\delta\varepsilon\mathrm{Var}_{\nu}[\varphi],$

where (i) uses Proposition 48 and the optional stopping theorem, (ii) uses the
second assumption of the theorem and (iii) uses the first assumption of the
theorem.

###### Proof of Theorem 47.

We have,

$\displaystyle\mathrm{Ent}_{\nu}[f]-\mathrm{Ent}_{\nu}[P^{(0)}f]$
$\displaystyle=\int_{\Omega}f(x)\log f(x)d\nu(x)-\int_{\Omega}P^{(0)}f(x)\log
P^{(0)}f(x)d\nu(x)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}\mathbb{E}\left[\int_{\Omega}f(x)\log
f(x)d\nu^{(i)}_{\mathfrak{a}}(x)-\int_{\Omega}P^{(\mathfrak{a})}f(x)\log
P^{(\mathfrak{a})}f(x)d\nu^{(i)}_{\mathfrak{a}}(x)\right]$
$\displaystyle=\mathbb{E}\left[\mathrm{Ent}_{\nu^{(i)}_{\mathfrak{a}}}[f]-\mathrm{Ent}_{\nu^{(i)}_{\mathfrak{a}}}[P^{(\mathfrak{a})}f]\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\geq}}\delta\mathbb{E}\left[\mathrm{Ent}_{\nu^{(i)}_{\mathfrak{a}}}[f]\right]$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\geq}}\delta\varepsilon\mathrm{Ent}_{\nu}[f],$

where (i) uses Proposition 48 and the optional stopping theorem, (ii) uses the
second assumption of the theorem and (iii) uses the first assumption of the
theorem.

##  5 Applications

In this section we provide several applications to demonstrate ways to obtain
mixing time results via our framework.

###  5.1 Glauber dynamics for Ising models

As a first example, we will prove a general theorem that provides a sufficient
condition for MLSI, which as a special case recovers two results: the first
one was shown in [EKZ21, AJK+21b] and establishes mixing time for Ising models
whose interaction matrix has an operator norm bounded by a constant and in
particular is relevant to the Sherrington-Kirkpatrick model in high-enough
temperatures. The second one concerns Ising models in the uniqueness regime
and improves upon the main theorem of [CFYZ21a].

Both applications will rely on the following result, which is obtained through
a simple combination of several ingredients of our framework.

######  Theorem 49.

Let $\nu$ be a measure on $\\{-1,1\\}^{n}$ and let $J$ be a positive-definite
$n\times n$ matrix. For any $0\leq\lambda\leq 1$ and every
$v\in\mathbb{R}^{n}$, consider the probability measure $\mu_{\lambda,v}$
defined by

$\frac{d\mu_{\lambda,v}}{d\nu}(x)\propto\exp\left(-\lambda\langle
x,Jx\rangle+\langle v,x\rangle\right).$ (35)

Suppose that, for some $\alpha:[0,1]\to\mathbb{R}_{+}$,

$\|\mathrm{Cov}(\mu_{\lambda,v})\|_{\mathrm{OP}}\leq\alpha(\lambda),~{}~{}\forall\lambda\in[0,1],~{}v\in\mathbb{R}^{n},$
(36)

and that for some $\varepsilon>0$,

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\mu_{1,v}))\geq\varepsilon,~{}~{}\forall
v\in\mathbb{R}^{n},$ (37)

where $P^{\mathrm{GD}}(\cdot)$ denotes the transition kernel of the Glauber
dynamics. Then,

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu))\geq\varepsilon\exp\left(-2\|J\|_{\mathrm{OP}}\int_{0}^{1}\alpha(\lambda)d\lambda\right).$

This theorem is particularly useful for measures with quadratic potentials, or
_Ising models_. For an $n\times n$ matrix $J$ and a vector
$v\in\mathbb{R}^{n}$, consider the probability measure defined by

$\nu_{J,v}(\\{x\\})\propto\exp\left(\langle x,Jx\rangle+\langle
x,v\rangle\right),$ (38)

referred to as the Ising measure with interaction matrix $J$ and external
field $v$.

If we apply the above theorem to the measure $\nu=\nu_{J,v}$ (and with $J$
taken to be the interaction matrix), we have that the measure $\mu_{1,v}$
defined in (35) is just a product measure, so that condition (37) is trivially
satisfied with $\varepsilon=\frac{1}{n}$. In order to successfully apply the
theorem, it therefore remains to verify condition (36). We will show how to do
so in two different settings.

###### Proof of Theorem 49.

Consider the localization process $(\nu_{t})_{t}$ corresponding to $\nu$
obtained via the stochastic localization (5), with the choice
$C_{t}=(2J)^{1/2}$, up to time $t=1$. Consider the transition kernel
$P^{\mathrm{GD}}(\nu_{1})$, hence, the random transition kernel associated to
the measure $\nu_{1}$ via the Glauber dynamics. We apply Theorem 47 in order
to obtain a lower bound on $\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu))$.

According to equation (6), $\nu_{t}$ has the form

$\nu_{t}(x)\propto\exp\left(-t\langle x,Jx\rangle+\langle
y_{t},x\rangle\right)\nu(x)$

for some stochastic process $y_{t}$, meaning that $\nu_{t}=\mu_{t,y_{t}}$.
Since in particular, $\nu_{1}=\mu_{1,y_{1}}$, the assumption (37) then amounts
to the fact that
$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu_{1}))\geq\varepsilon$, which fulfills
the second condition of Theorem 47.

Next, the assumption (36) tells us that

$\|\mathrm{Cov}(\nu_{t})\|_{\mathrm{OP}}\leq\alpha(t),\forall t\in[0,1].$

By applying Lemma 40 with the choice $A=\alpha(t)\mathbf{I}_{n}$ and
$C=(2J)^{1/2}$, we conclude that $\nu_{t}$ is $\alpha$-entropically stable
with respect to $\psi(x,y)=\frac{1}{2}\left|(2J)^{1/2}(x-y)\right|^{2}$ with
$\alpha=2\|J\|_{\mathrm{OP}}\alpha(t)$. Invoking Proposition 39 gives the
approximate-entropy-conservation bound

$\mathbb{E}\left[\mathrm{Ent}_{\nu_{1}}[f]\right]\geq
e^{-2\|J\|_{\mathrm{OP}}\int_{0}^{1}\alpha(t)dt}\mathrm{Ent}_{\nu}[f].$

Therefore, condition 1 of Theorem 47 is satisfied with
$\alpha=e^{-2\|J\|_{\mathrm{OP}}\int_{0}^{1}\alpha(t)dt}$, and we conclude
that $\mathrm{\rho_{LS}}(P)\geq\varepsilon
e^{-2\|J\|_{\mathrm{OP}}\int_{0}^{1}\alpha(t)dt}$. This completes the proof.

####  5.1.1 Mixing under a spectral condition on the interaction matrix

It turns out that if the interaction matrix has operator norm bounded by a
certain constant, then the covariance matrix of the model is also bounded. The
following lemma is based on the decomposition obtained by Bauerschmidt and
Bodineau [BB19]. For completeness, we include a proof in Appendix B.

######  Lemma 50.

Let $J$ be a positive-definite matrix with $\|J\|_{\mathrm{OP}}<\frac{1}{2}$
and let $v\in\mathbb{R}^{n}$. One has

$\|\mathrm{Cov}(\nu_{J,v})\|_{\mathrm{OP}}\leq\frac{1}{1-2\|J\|_{OP}}.$

Combining the lemma with Theorem 49, we obtain

######  Corollary 51.

Let $J$ be a positive-definite matrix with $\|J\|_{\mathrm{OP}}<\frac{1}{2}$
and let $v\in\mathbb{R}^{n}$. The Glauber dynamics for $\nu=\nu_{J,v}$ mixes
in time $O(n\log n)$.

###### Proof.

An application of Lemma 50 gives

$\|\mathrm{Cov}(\mu_{\lambda,v})\|_{\mathrm{OP}}\preceq\frac{1}{1-2(1-\lambda)\|J\|_{\mathrm{OP}}},$

so the assumption (36) holds with $\alpha(\lambda)$ equal to the right-hand
side. Assumption (37) holds with $\delta=1/n$ since $\mu_{1,v}$ is a product
measure. The conclusion of the Theorem 49 tells us that

$\displaystyle\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu_{J,v}))$
$\displaystyle\geq\frac{1}{n}\exp\left(-\int_{0}^{1}\frac{2}{1/\|J\|_{\mathrm{OP}}-2(1-\lambda)}d\lambda\right)$
$\displaystyle=\frac{1}{n}(1-2\|J\|_{\mathrm{OP}}).$

The proof is complete via fact 2.

######  Remark 52.

The above corollary implies an optimal mixing bound for Glauber dynamics on
the Sherrington-Kirkpatrick model up to inverse temperature $\beta=1/4$ (see
[EKZ21] for a detailed discussion on the Sherrington-Kirkpatrick model). Very
recently, El Alaoui, Montanari and Sellke [AMS22] gave a polynomial time
sampling algorithm which is valid all the way to the critical temperature
$\beta=1/2$. The idea behind their algorithm is to simulate the stochastic
localization process. To do so, one needs to estimate the center of mass of
tilted measures which, in turn, is done using approximate message passing.

####  5.1.2 Near-critical ferromagnetic Ising models

Next, we show how to recover a variant of the result which appears in the very
recent paper of Bauerschmidt and Dagallier [BD22]. Consider a measure of the
form (38) which is _ferromagnetic_ in the sense that $J_{i,j}\geq 0$ for all
$i\neq j$. For every $\lambda\in(0,1)$ define

$\chi(\lambda):=\|\mathrm{Cov}(\nu_{\lambda J,0})\|_{\mathrm{OP}}$

In the ferromagnetic case, following theorem, due to Ding, Song and Sun, is
very helpful towards verifying assumption (36) in Theorem 49.

######  Theorem 53.

([DSS22]) For any interaction matrix $J$ which is ferromagnetic (hence
$J_{i,j}\geq 0$ for all $i\neq j$), for all $i\neq j$ and for all
$v\in\mathbb{R}^{n}$, we have

$\mathrm{Cov}(\nu_{J,v})_{i,j}\leq\mathrm{Cov}(\nu_{J,0})_{i,j}.$

By the above combined with the Perron-Frobenius theorem, it follows that

$\|\mathrm{Cov}(\nu_{\lambda
J,v})\|_{\mathrm{OP}}\leq\chi(\lambda),~{}~{}\forall v\in\mathbb{R}^{n}.$

Therefore, invoking Theorem 49 with $\mu_{\lambda,v}=\nu_{(1-\lambda)J,v}$
immediately yields the following.

######  Corollary 54.

For any ferromagnetic interaction matrix $J$ which is positive definite, we
have

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu_{J,v})\geq\frac{1}{n}\exp\left(-2\|J\|_{\mathrm{OP}}\int_{0}^{1}\chi(\lambda)d\lambda\right).$

As noted in [BD22], the positive definiteness can always be imposed by adding
a diagonal matrix without changing the corresponding Ising model.

####  5.1.3 Graphical Ising model in the uniqueness regime

For a graph $G=(V,E)$ with $V=[n]$ and $\beta\in\mathbb{R}$, the corresponding
Ising model is defined as

$\nu_{G,\beta}(x)\propto\exp\left(\langle x,v\rangle+\beta\sum_{(i,j)\in
E}\mathbf{1}_{\\{x_{i}=x_{j}\\}}\right).$ (39)

We say that the measure $\nu_{G,\beta}$ satisfies the tree-uniqueness
condition if

$\exp(|\beta|)<\frac{\Delta(G)-\delta}{\Delta(G)-2+\delta},$ (40)

for $\delta\in(0,1)$, where $\Delta(G)\geq 3$ is the maximum degree of the
graph. The following result was proven in [CLV21] (see also [CFYZ21a, Lemma
8.3]).

######  Theorem 55.

(Spectral independence for the Ising model). Let $\nu=\nu_{G,\beta}$ be an
Ising model defined as in (39) which satisfies the tree-uniqueness condition
(40). Then for any external field $v\in\mathbb{R}^{n}$,

$\rho(\mathbf{\Psi}(\mathcal{T}_{v}\nu))\leq\frac{2}{\delta}.$

Given a graph $G=(V,E)$, define a matrix $J=J_{G}$ by

$J_{i,j}=\frac{1}{2}\left(\mathbf{1}_{\\{(i,j)\in
E)\\}}+\mathbf{1}_{\\{i=j\\}}\mathrm{deg}_{G}(i)\right).$

It is straightforward to check that

$\sum_{(i,j)\in E}\mathbf{1}_{\\{x_{i}=x_{j}\\}}=\langle x,J_{G}x\rangle,$

and that $J_{G}$ is positive-definite.

######  Corollary 56.

Any graphical Ising model $\nu$ of the form (39) which satisfies (40), one has

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu))\geq\frac{\exp(-8/\delta)}{n}.$

Consequently, the mixing time for Glauber dynamics is $O(n\log n)$.

###### Proof.

First, we deal with the case $\beta>0$. Apply Theorem 49 with the choice
$J=\beta J_{G}$. Observe that for all $\lambda\in[0,1]$, the measure
$\mu_{\lambda,v}$ defined in (35) is of the form (39), with a smaller value of
$\beta$, and therefore $\mu_{\lambda,v}$ is also in the uniqueness regime. An
application of Theorem 55 ensures that
$\rho(\mathbf{\Psi}(\mu_{\lambda,v}))\leq\frac{2}{\delta}$. By Fact 23 we have

$\|\mathrm{Cov}(\mu_{\lambda,v})\|_{\mathrm{OP}}\leq\|\mathbf{Cor}(\mu_{\lambda,v})\|_{\mathrm{OP}}\leq\frac{2}{\delta},$

so (36) holds with $\alpha(\lambda)=2/\delta$. Moreover, since $\mu_{1,v}$ is
a product measure, condition (37) holds with $\varepsilon=1/n$. Therefore, we
can conclude by Theorem 49 that

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu))\geq\frac{1}{n}\exp\left(-4\frac{\beta\|J_{G}\|_{\mathrm{OP}}}{\delta}\right)\geq\frac{1}{n}e^{-8/\delta}.$

The last step follows because $J_{G}=\mathbf{I}_{n}-\frac{1}{2}L^{\text{sym}}$
where $L^{\text{sym}}$ is the symmetrically normalized Laplacian which has
eigenvalues between $0$ and $2$; and
$\beta<\log\left(\frac{\Delta(G)-\delta}{\Delta(G)-2+\delta}\right)\leq 2$.
Second, the case $\beta=0$ is trivial because it becomes a product measure.
Finally, for the case $\beta<0$, we observe that

$\displaystyle-\left|\beta\right|\left\langle
x,J_{G}x\right\rangle=\left|\beta\right|\left(\left\langle
x,(\mathbf{I}_{n}-J_{G})x\right\rangle-\left\langle
x,x\right\rangle\right)==\left|\beta\right|\left(\left\langle
x,(\mathbf{I}_{n}-J_{G})x\right\rangle-n\right).$

$\mathbf{I}_{n}-J_{G}$ is positive-definite and has operator norm bounded by
$1$. Using the same argument as the case $\beta>0$ but with $J_{G}$ replaced
by $\mathbf{I}_{n}-J_{G}$, we obtain the same MLSI lower bound.

###  5.2 Sampling from strongly log-concave measures via a Restricted Gaussian
Oracle

Let $\nu$ be a log-concave measure on $\mathbb{R}^{n}$, hence, a measure of
the form

$\frac{\nu(dx)}{dx}=\exp(-V(x)),~{}~{}V:\mathbb{R}^{n}\to\mathbb{R}\mbox{
convex}.$

We assume that it is uniformly (or strongly) log-concave, namely that

$\nabla^{2}V(x)\succeq\mu\mathbf{I}_{n},~{}~{}\forall x\in\mathbb{R}^{n}.$
(41)

Let $(\nu_{t})_{t}$ be the process attained from $\nu$ via the stochastic
localization scheme (5) with the choice $C_{t}\equiv\mathbf{I}_{n}$. According
to equation (6), $\nu_{t}$ has the form

$\frac{d\nu_{t}}{dx}\propto\exp\left(-\tilde{V}(x)-\frac{t}{2}|x|^{2}\right)$
(42)

where $\tilde{V}(x)$ is convex (it is an exponential tilt of $V(x)$). The
following well-known bound goes back to Brascamp and Lieb.

######  Theorem 57.

If $\rho$ is a measure on $\mathbb{R}^{n}$ of the form
$\frac{\rho(dx)}{dx}\propto\exp(-U(x))$ that satisfies the uniform convexity
condition

$\nabla^{2}U(x)\succeq\alpha\mathbf{I}_{n},~{}~{}~{}\forall
x\in\mathbb{R}^{n},$

then $\|\mathrm{Cov}(\rho)\|_{\mathrm{OP}}\leq\frac{1}{\alpha}$.

Equations (41) and (42) imply that $\nu_{t}$ has the form
$\frac{d\nu_{t}(x)}{dx}=\exp(-U(x))$ with

$\nabla^{2}U(x)\succeq(\mu+t)\mathbf{I}_{n},~{}~{}\forall x\in\mathbb{R}^{n}.$

Therefore, the above theorem gives

$\|\mathrm{Cov}(\mathcal{T}_{v}\nu_{t})\|_{\mathrm{OP}}\leq\frac{1}{\mu+t},~{}~{}~{}\forall
v\in\mathbb{R}^{n}.$ (43)

An application of Lemma 40 gives that $\nu_{t}$ is $\alpha$-entropically-
stable with respect to $\psi(x,y)=\frac{1}{2}|x-y|^{2}$, with
$\alpha=\frac{1}{\mu+t}$. Proposition 39 now gives the approximate
conservation of entropy bound

$\mathbb{E}\left[\mathrm{Ent}_{\nu_{T}}[f]\right]\geq\mathrm{Ent}_{\nu}[f]\exp\left(-\int_{0}^{T}\frac{1}{\mu+t}dt\right)=\frac{\mu}{\mu+T}\mathrm{Ent}_{\nu}[f],$

for an arbitrary $f:\mathbb{R}^{n}\to\mathbb{R}^{+}$ such that $\int fd\nu>0$.
Using equation (11), this gives

$\mathrm{\rho_{LS}}(P^{\mathrm{RGD}_{\eta}}(\nu))\geq\frac{\mu}{\mu+1/\eta},$

where $P^{\mathbf{RGD}_{\eta}}(\nu)$ is the transition kernel of the
restricted Gaussian dynamics (Definition 15 above). We have proved:

######  Theorem 58.

If $\nu$ is a $\mu$-strongly log-concave measure on $\mathbb{R}^{n}$, then the
associated restricted Gaussian dynamics with parameter $\eta$ satisfies
$\mathrm{\rho_{LS}}(P^{\mathrm{RGD}_{\eta}}(\nu))\geq\frac{\mu}{\mu+1/\eta}$.

The above theorem not only recovers Theorem 1.1 in [LST21], but also resolves
the open problem discussed in section 1.4 of the same paper: it provides a
proof to show that the Restricted Gaussian Dynamics mixes in $\eta\mu\log(n)$
steps when started from any $O(\exp(n))$-warm start in the case $\eta<1/\mu$.
As defined in [LST21], an initial measure $\rho$ is a $\beta$-warm start with
respect to $\nu$ if $\frac{d\rho}{d\nu}(x)\leq\beta$ everywhere. The
applications of the above theorem includes improving dependency of condition
number dependency of Markov chains for log-concave sampling and introducing
new sampling algorithms for composite log-concave distributions and log-
concave finite sums, which has been extensively discussed in [LST21].

###  5.3 A spectral-independence based condition for fast mixing and
applications to sampling from the hardcore model

In this section we present the main application of the negative-fields
localization, giving a sufficient condition for fast mixing. In particular, it
provides an optimal mixing time bound for sampling the hardcore model via
Glauber dynamics.

Recall that, for $u\in\\{-1,0,1\\}$, we define the $u$-pinning
$\mathcal{R}_{u}\nu$ to be the restriction of $u$ to the subcube
$S_{u}:=\left\\{x\in\\{-1,1\\}^{n};~{}x_{i}u_{i}\geq 0,~{}\forall
i\in[n]\right\\}$ and that $\mathcal{T}_{v}\nu$ is the $v$-exponential tilt of
$\nu$.

The following definition relates the marginals of the pinned distribution to
those of the original distribution and lower bounds the marginals in a one-
sided fashion.

######  Definition 59.

For $K>1$, a measure $\nu$ on $\\{-1,1\\}^{n}$ has $K$-tame marginals if for
every $i\in[n]$ and for every $u,w\in\\{-1,0,1\\}^{n}$ with
$\text{supp}(u)\cap\text{supp}(w)=\emptyset$ with $u_{i}=w_{i}=0$, we have

$\displaystyle\frac{1+\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{u}\nu)}{1-\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{u}\nu)}$
$\displaystyle\leq
K\frac{1+\mathbf{b}_{i}(\mathcal{R}_{u}\nu)}{1-\mathbf{b}_{i}(\mathcal{R}_{u}\nu)},\text{
and }$ (44) $\displaystyle 1-\mathbf{b}_{i}(\mathcal{R}_{u}\nu)$
$\displaystyle\geq\frac{1}{K}.$ (45)

Our main aim is to establish the following sufficient condition for a MLSI:
Given a measure $\nu$ on $\\{-1,1\\}^{n}$, if a MLSI can be established for a
perturbed measured obtained after applying an external field $v$, and if the
correlation matrix has bounded operator norm for any external field $\lambda
v$, $\lambda\in[0,1]$ and under all pinnings, then the original measure
satisfies a MLSI.

######  Theorem 60.

Let $s>0$. Let $\nu$ be a measure on $\\{-1,1\\}^{n}$ such that for any
$\lambda\in[0,s]$, $\mathcal{T}_{-\lambda\vec{\mathbf{1}}}\nu$ has $K$-tame
marginals. Define $\vec{\mathbf{1}}:=(1,...,1)$. Suppose that for any
$\lambda\in[0,s]$ and $u\in\\{-1,0,1\\}^{n}$, we have

$\left\|\mathbf{Cor}(\mathcal{R}_{u}\mathcal{T}_{-\lambda\vec{\mathbf{1}}}\nu)\right\|_{\mathrm{OP}}\leq\eta.$
(46)

Moreover, assume that for all $u\in\\{-1,0,1\\}^{n}$,

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\mathcal{R}_{u}\mathcal{T}_{-s\vec{\mathbf{1}}}\nu))\geq\delta.$
(47)

Then we have

$\mathrm{\rho_{LS}}(P^{\mathrm{GD}}(\nu))\geq\delta e^{-cK^{4}\eta},$

for a universal constant $c>0$.

######  Remark 61.

In the above theorem we considered the “path” of tilts
$\\{-\lambda\vec{\mathbf{1}};\lambda\in[0,s]\\}$. The same proof works for the
more general case that we consider $\mathcal{T}_{v(\lambda)}\nu$ for an
arbitrary curve $v:[0,1]\to\mathbb{R}^{n}$. The special case
$v(\lambda)=-\lambda\vec{\mathbf{1}}$ is sufficient for the applications that
we know of, which is why we chose to stick to it for the sake of simplicity.

###### Proof of Theorem 60.

The main proof strategy is to use the negative-fields-localization
(constructed in Section 2.4.4) as an annealing scheme for the measure. Namely,
we apply Proposition 18 with the choice $v(t)=-t\vec{\mathbf{1}}$ to obtain a
localization process $(\nu_{t})_{t}$. We concatenate this process to the
coordinate-by-coordinate localization scheme at time $s$ and apply theorem 47,
which gives us a MLSI bound for the Glauber dynamics $P^{\mathrm{GD}}(\nu)$.

According to Proposition 18, for every $t>0$ there exists
$u(t)\in\\{-1,0,1\\}^{n}$ such that

$\nu_{t}=\mathcal{T}_{-t\vec{\mathbf{1}}}\mathcal{R}_{u(t)}\nu.$

Therefore, condition 2 of theorem 47 follows immediately from equation (47).

It remains to show that condition 1 of Theorem 47 is satisfied, which boils
down to the approximate entropy conservation bound

$\mathbb{E}[\mathrm{Ent}_{\nu_{s}}[f]]\geq
e^{-64K^{2}e^{s}\eta}\mathrm{Ent}_{\nu}[f],$ (48)

for an arbitrary function $f:\\{-1,1\\}^{n}\to\mathbb{R}_{+}$.

Fix $t\in[0,s]$. We aim to apply Theorem 42 to the measure $\nu_{t}$, which
should be understood as a measure on the sub-cube
$S_{u(t)}=\\{x\in\\{-1,1\\}^{n};~{}x_{i}u(t)_{i}\geq 0,~{}\forall i\in[n]\\}$.
To check that condition (30) is fulfilled, let $\tilde{u}\in\\{-1,0,1\\}^{n}$
be such that $\tilde{u}_{i}u(t)_{i}=0$ for all $i\in[n]$ (which amounts to all
valid pinning for a function on $S_{u(t)}$), then

$\displaystyle\left\|\mathbf{Cor}(\mathcal{R}_{\tilde{u}}\nu_{t})\right\|_{\mathrm{OP}}$
$\displaystyle=\left\|\mathbf{Cor}(\mathcal{R}_{\tilde{u}}\mathcal{R}_{u(t)}\mathcal{T}_{-t\vec{\mathbf{1}}}\nu)\right\|_{\mathrm{OP}}$
$\displaystyle=\left\|\mathbf{Cor}(\mathcal{R}_{\tilde{u}+u(t)}\mathcal{T}_{-t\vec{\mathbf{1}}}\nu)\right\|_{\mathrm{OP}}\overset{\eqref{eq:smallcov1}}{\leq}\eta.$

Define $F_{t}=\left\\{i\in[n];u_{i}(t)=0\right\\}$, the set of coordinates
which have not been pinned yet. In order to verify condition (31) and (32) for
$\nu_{t}$, we use the fact that $\nu_{t}$ is obtained by pinning
$\mathcal{T}_{-t\vec{\mathbf{1}}}\nu$ which has $K$-tame martingales. First,
for all $i\in F_{t}$ and all $u(t)\perp\tilde{u}\in\\{-1,0,1\\}^{n}$ with
$\tilde{u}_{i}=0$,
$1-\mathbf{b}_{i}(\mathcal{R}_{\tilde{u}}\nu_{t})=1-\mathbf{b}_{i}(\mathcal{R}_{\tilde{u}}\mathcal{R}_{u(t)}\mathcal{T}_{-t\vec{\mathbf{1}}}\nu)\geq\frac{1}{K}$,
which verifies condition (32) for $\nu_{t}$. Second, using the $K$-tame
marginals of $\mathcal{T}_{-t\vec{\mathbf{1}}}\nu$, we obtain

$\displaystyle\frac{1+\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{\tilde{u}}\nu_{t})}{1-\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{\tilde{u}}\nu_{t})}$
$\displaystyle=\frac{1+\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{\tilde{u}}\mathcal{R}_{u(t)}\mathcal{T}_{-t\vec{\mathbf{1}}}\nu)}{1-\mathbf{b}_{i}(\mathcal{R}_{w}\mathcal{R}_{\tilde{u}}\mathcal{R}_{u(t)}\mathcal{T}_{-t\vec{\mathbf{1}}}\nu)}$
$\displaystyle\leq
K\frac{1+\mathbf{b}_{i}(\mathcal{R}_{w}\nu_{t})}{1-\mathbf{b}_{i}(\mathcal{R}_{w}\nu_{t})},$

which verifies condition (31) for $\nu_{t}$. Apply Theorem 42 to $\nu_{t}$, we
obtain that $\nu_{t}$ is $cK^{4}\eta$-entropically stable with respect to the
function $H(x,y)$, where $c$ is a universal constant. We can finally use
Proposition 41 which gives that for $t,h>0$,

$\mathbb{E}[\mathrm{Ent}_{\nu_{t+h}}[f]|u(t)]\geq\mathrm{Ent}_{\nu_{t}}[f](1-cK^{4}\eta
h)+o(h).$

By integrating this inequality, we finally get

$\mathbb{E}[\mathrm{Ent}_{\nu_{s}}[f]]\geq\mathrm{Ent}_{\nu}[f]\exp\left(-cK^{4}\eta\right).$

Both conditions of Theorem 47 are satisfied, and we conclude the proof.

####  5.3.1 Application to an optimal mixing bound for Glauber dynamics in the
hardcore model

Given a graph $G=(V,E)$, we define the set of all independent assignments as

$\displaystyle\mathcal{I}_{G}:=\left\\{x\in\\{-1,1\\}^{V}:~{}x_{i}+x_{j}\leq
1,~{}\forall(i,j)\in E\right\\}.$

If we associate a point $x\in\\{-1,1\\}^{V}$ the set $A(x)=\\{v\in
V;x_{v}=1\\}$, then $A(\mathcal{I}_{G})$ is the family of independent sets in
$G$.

For $\lambda\in(0,\infty)$ let $\rho_{\lambda}$ be the product probability
measure on $\\{-1,1\\}^{V}$ defined by

$\rho_{\lambda}(\\{x\\})=\prod_{v\in
V}\frac{\mathbf{1}_{\\{x_{v}=-1\\}}+\lambda\mathbf{1}_{\\{x_{v}=1\\}}}{1+\lambda}.$

The hardcore model on $G$ with fugacity $\lambda$ is a probability measure on
$\\{-1,1\\}^{V}$ defined by

$\nu_{G,\lambda}(\\{x\\}):=\frac{\rho_{\lambda}(\\{x\\})\mathbf{1}_{\\{x\in\mathcal{I}_{G}\\}}}{\rho_{\lambda}(\mathcal{I}_{G})}.$

A hardcore model with fugacity $\lambda$ is called $\delta$-unique if
$\lambda\leq(1-\delta)\lambda_{\Delta}$, where the critical fugacity is

$\displaystyle\lambda_{\Delta}=\frac{(\Delta-1)^{\Delta-1}}{(\Delta-2)^{\Delta}},$
(49)

and where $\Delta$ is the maximal degree of $G$.

Our goal is to prove the following theorem, which asserts that the Glauber
dynamics mixes in time $O(n\log n)$ in the uniqueness regime.

######  Theorem 62.

Given a graph $G=(V,E)$. $\left|V\right|=n$ and $\lambda>0$, let
$\nu=\nu_{G,\lambda}$ be the hardcore model on $G$ with fugacity $\lambda$.
Suppose that $\nu$ is $\delta$-unique for some $\delta>0$. Let $\mu_{0}$ be an
arbitrary initial distribution supported on $\mathcal{I}_{G}$. Then there
exists a universal constant $c>0$, such that

$\displaystyle
t_{\mathrm{mix}}(P^{\mathrm{GD}}(\nu),\varepsilon;\mu_{0})\leq\exp\left(\frac{c}{\delta}\right)\left(n\log(n)+3n\log(1/\varepsilon)\right).$

Proving mixing bounds for the hardcore model has been one of the central
applications of the spectral and entropic independence frameworks. This model
has inspired the first paper which put forth the notion of spectral
independence as well as many of the following works. Let us summarize the
progress made so far.

  * •

Anari, Liu and Oveis Gharan were the first to introduce the notion of spectral
independence in [ALOG20], and proved an $n^{\exp(O(1/\delta))}$ mixing time.

  * •

Chen, Liu and Vigoda [CLV21] proved tight bounds on spectral independence,
gave an improved $n^{O(1/\delta)}$ mixing time.

  * •

Chen, Liu and Vigoda [CLV20] extended the framework towards MLSI bounds and
proved that $\Delta^{O(\Delta^{2}/\delta)}n\log(n)$, which in particular gives
an optimal bound for constant $\Delta$.

  * •

Jain, Pham and Vuong [AJK+21a] proved a mixing time of
$\Delta^{O(1/\delta)}n^{2}$.

  * •

Chen, Feng, Yin and Zhang [CFYZ21b], in Theorem 1.3, obtained an optimal bound
for the relaxation time, which implies a mixing time of
$C(\delta)n^{2}\log(\Delta)$.

  * •

Anari et al. [AJK+21a, Theorem 1], showed that a variant of Glauber dynamics
called the balanced Glauber dynamics gives an $O_{\delta}(n\log(n))$ mixing
time.

Our result, Theorem 62 is the first to give an optimal mixing bound for the
(usual) Glauber dynamics.

The proof combines many of ingredients developed in our framework, together
with the idea of using a certain “restricted” type of entropy decay.

####  5.3.2 Properties of the hardcore distribution

In this subsection, we collect four properties of the hardcore distribution:
spectral independence for all negative tilts and all pinnings, marginal upper
and lower bounds, the fact that exponentially tilt hardcore model remains a
hardcore model and MLSI coefficient for hardcore model with small fugacity.
Throughout this section we fix graph $G=(V,E)$ with maximum degree $\Delta$, a
fugacity $\lambda\in(0,\infty)$ and define $\nu=\nu_{G,\lambda}$ to be the
corresponding hardcore model. Without loss of generality, we identify $V$ with
$[n]$ for simplicity.

The first lemma establishes spectral independence of all negative tilts and
all pinnings of the hardcore distribution, and was proved in Lemma 8.4 of
[CFYZ21b] extending the analyses in [CLV20].

######  Lemma 63.

Consider the hardcore model $\nu=\nu_{G,\lambda}$ with $\Delta=\Delta(G)\geq
3$. Furthermore, suppose that $\nu$ is $\delta$-unique on $G$. Then for all
$u\in\left\\{-1,0,1\right\\}^{n}$ and for every vector $v\in(-\infty,0]^{V}$,
we have

$\displaystyle\left\|\mathbf{Cor}(\mathcal{T}_{v}\mathcal{R}_{u}\nu)\right\|_{\mathrm{OP}}\leq\frac{144}{\delta}.$

The next lemma gives bounds for the marginals of the hardcore distribution. It
was essentially proven in [AJK+21a, Proposition 50], but we provide a proof in
Appendix C for completeness.

######  Lemma 64.

Let $\nu=\nu_{G,\lambda}$ with $\Delta(G)\geq 3$. Then for any $v\in V$, for
any $u\in\left\\{-1,0,1\right\\}^{n}$ which sets all neighbors of $v$ to $0$
(i.e., satisfying $u_{a}=0,\forall a\in N_{v}$), we have

$\displaystyle\frac{\lambda}{1+\lambda}\left(\frac{1}{1+\lambda}\right)^{\left|N_{v}\right|}\leq{\mathbb{P}}_{\sigma\sim\nu}\left(\sigma_{v}=+1\mid\sigma_{i}u_{i}\geq
0,\forall i\in[n]\right)\leq\frac{\lambda}{1+\lambda}.$

Moreover, if the model is $\delta$-unique, namely
$\lambda\leq(1-\delta)\lambda_{\Delta}$, then

$\displaystyle\frac{\lambda}{1+\lambda}e^{-3e^{2}}\leq{\mathbb{P}}_{\sigma\sim\nu}\left(\sigma_{v}=+1\mid\sigma_{i}u_{i}\geq
0,\forall i\in[n]\right)\leq\frac{\lambda}{1+\lambda}.$

Recall that $\vec{\mathbf{1}}=(1,\dots,1)$. The next lemma shows that the
exponentially tilted hardcore model remains a hardcore model.

######  Lemma 65.

For every $G$ and $\lambda$, we have for all $t>0$,