Entropic independence via sparse localization

1. Problem Statement and Motivation

Context:
The paper addresses the derivation of functional inequalities, specifically Modified Log-Sobolev Inequalities (mLSIs), for high-dimensional discrete distributions. Proving mLSIs is crucial for establishing sharp mixing time bounds for Markov chains, concentration inequalities, and quantitative stability.

The "Annealing" Approach:
A standard modern strategy for proving mLSIs involves an "annealing" (or interpolation) path of measures $\nu = \nu^{(0)} \leadsto \dots \leadsto \nu^{(T)}$. This process has two steps:

1. Reduction to an easy regime: Showing entropy does not decay too quickly along the path (requiring Entropic Independence).
2. Handling the easy regime: Proving the mLSI for the final, tractable measure.

The Gap:
The focus of this paper is Step (i). Existing sufficient criteria for entropic independence (e.g., Chen–Liu–Vigoda, Anari et al., Chen–Eldan) typically require uniform control over all possible pinnings (conditionings) of the base measure. Specifically, they demand:

• Spectral independence (bounded influence matrix) under all pinnings.
• Uniform marginal boundedness under all pinnings.

The Conflict:
In many natural models, particularly those involving conservative dynamics (e.g., the uniform distribution on independent sets of fixed size in bounded-degree graphs), these "all pinnings" requirements are too stringent. While the system exhibits strong mixing properties, conditioning on arbitrary subsets of variables can create highly adversarial, degenerate intermediate distributions where independence bounds fail. However, along the specific "localization path" used in annealing arguments, only a sparse family of pinnings (fixing a small fraction of coordinates) is ever encountered.

Core Question:
Can one deduce entropic independence if independence and marginal bounds are only guaranteed for a sparse family of pinnings (fixing at most $cn$ coordinates for small $c$), rather than all pinnings?

---

2. Methodology and Key Concepts

The authors introduce a framework called Sparse Localization.

A. Sparse $\ell_2$-Independence

Instead of requiring spectral independence for all pinnings, the authors assume it holds only for pinnings that fix at most $c n$ coordinates.

• Definition: A measure $\nu$ is $c$-sparse $\alpha$-$\ell_2$-independent if for any pinning vector $u \in \{-1, 0, 1\}^n$ with support size $|\text{supp}(u)| \le \lceil cn \rceil$, the operator norm of the influence matrix of the pinned measure is bounded: $\|\Psi(R_u \nu)\|_{op} \le \alpha$.
• Relation to Spectral Independence: Under marginal boundedness, $\ell_2$-independence (operator norm of the influence matrix) is equivalent to spectral independence (operator norm of the correlation matrix) up to a constant factor.

B. The Main Theoretical Tool: Quadratic Stability

The paper establishes a Quadratic Stability Inequality on the discrete cube. This inequality bounds the squared $\ell_2$ distance between mean vectors by the Kullback-Leibler (KL) divergence, but with a loss factor dependent on sparsity.

Theorem 1.5 (Quadratic Stability from Sparse $\ell_2$-Independence):
If $\nu$ is $\alpha$-$\ell_2$-independent restricted to sparse pinnings (support $\le cn$), then for any $\mu \ll \nu$:
$$\|m(\mu) - m(\nu)\|_2^2 \le \frac{8\alpha}{c} \text{KL}(\mu \| \nu)$$

• Significance: When $c=1$ (full localization), this recovers the Chen–Eldan result. When $c$ is small, the bound holds but incurs a multiplicative loss of $O(c^{-1})$.

C. Proof Techniques

The proof of the main theorem adapts the Chen–Eldan localization martingale framework but introduces two novel modular components:

1. Restricted Localization Lipschitz Lemma (Section 4):

   • The authors construct a continuous-time jump process (martingale) that localizes the measure.
   • Crucially, they ensure the process only visits pinnings within the allowed sparse family ($\text{sign}(\text{Sparse}_c)$).
   • They prove that $\ell_2$-independence over this restricted set implies the mean map is Lipschitz continuous along sparse directions.

2. Sparse Convex Duality (Section 5):

   • Standard proofs use the Donsker–Varadhan variational formula with all linear test functions.
   • The authors restrict the test functions to sparse linear functionals (vectors with support $\le cn$).
   • They compute the restricted quadratic conjugate explicitly. This involves Ky Fan norms (the sum of the largest $m$ squared coordinates).
   • The Loss Factor: The inequality $\|x\|_2^2 \le \frac{n}{m} \|x\|_{2,(m)}^2$ (where $m \approx cn$) introduces the $c^{-1}$ factor. This is the unique point where the sparsity constraint degrades the constant.

---

3. Key Contributions

1. Introduction of Sparse Localization:
   The paper formalizes a framework where entropic independence is derived from independence properties that hold only for a sparse subset of conditionings. This matches the reality of many "conservative" dynamics where full localization is impossible or unnecessary.

2. Explicit Loss Factor:
   The authors provide a rigorous proof that sparse independence implies entropic independence with an explicit, manageable loss factor of $O(c^{-1})$. This quantifies the trade-off between the sparsity of the conditioning and the strength of the resulting inequality.

3. Resolution of a Critical Gap in Independent Sets:
   The paper provides a rigorous proof for the entropy conservation step in the analysis of the down-up walk on fixed-size independent sets in bounded-degree graphs.

   • Previous work (e.g., [8]) claimed this result but relied on assumptions (spectral independence for all pinnings) that were not actually satisfied in this model.
   • The authors show that while full independence fails, sparse independence holds, which is sufficient to prove the mLSI and optimal mixing times.

---

4. Main Results

Theorem 1.2 (Entropic Independence):
Let $\nu$ be a probability measure on the $k$-slice of $[n]$. If:

1. Marginal Lower Bound: Every coordinate has probability $\ge b$ of being selected (or 0).
2. Sparse $\ell_2$-Independence: The measure is $\alpha$-$\ell_2$-independent for all pinnings fixing $\le cn$ coordinates.

Then $\nu$ is $C$-entropically independent with $C = \frac{2\alpha}{bc}$.

Application: Down-Up Walk on Independent Sets (Section 6):

• Model: Uniform distribution on independent sets of size $k$ in a graph with max degree $\Delta$.
• Result: The authors prove that for $k$ in the "algorithmic tractability regime" (specifically $k \approx \Omega(n)$), the measure satisfies the conditions for sparse localization.
• Outcome: They rigorously prove the entropy factorization (annealing step) required to show that the down-up walk mixes in optimal time. This fixes a gap in the literature where previous arguments incorrectly assumed uniform spectral independence.

---

5. Significance

• Theoretical Advancement: It decouples the requirement for "global" spectral independence from the derivation of functional inequalities. It demonstrates that local-to-global arguments can succeed even when the "local" properties are only available for a restricted, sparse set of conditionings.
• Methodological Innovation: The use of Ky Fan norms in the convex duality step to handle sparse test functions is a novel technical contribution that may be applicable to other problems involving restricted conditioning.
• Practical Impact: It validates the mixing time analysis for the down-up walk on independent sets, a fundamental problem in statistical physics and computer science (related to the hard-core model). It confirms that optimal mixing holds in regimes where previous rigorous proofs were incomplete.
• Broader Applicability: The framework suggests that many other "conservative" systems (where mass is preserved, e.g., fixed particle number) might be amenable to mLSI proofs via sparse localization, even if they fail standard uniform independence criteria.

In summary, this paper bridges a critical gap between the theoretical requirements for proving mixing times and the actual properties of complex combinatorial distributions, providing a robust tool for analyzing high-dimensional discrete systems where full localization is infeasible.