Talagrand's convolution conjecture up to loglog via perturbed reverse heat
By: Yuansi Chen
Potential Business Impact:
Makes guessing better for computers.
We prove that under the heat semigroup $(P_τ)$ on the Boolean hypercube, any nonnegative function $f: \{-1,1\}^n \to \mathbb{R}_+$ exhibits a uniform tail bound that is better than that by Markov's inequality. Specifically, for any $η> e^3$ and $τ> 0$, \begin{align*} \mathbb{P}_{X \sim μ}\left( P_τf(X) > η\int f dμ\right) \leq c_τ\frac{ \log \log η}{η\sqrt{\log η}}, \end{align*} where $μ$ is the uniform measure on the Boolean hypercube $\{-1,1\}^n$ and $c_τ$ is a constant that only depends on $τ$. This resolves Talagrand's convolution conjecture up to a dimension-free $\log\log η$ factor. Its proof relies on properties of the reverse heat process on the Boolean hypercube and a coupling construction based on carefully engineered perturbations of this reverse heat process.
Similar Papers
Simple and Sharp Generalization Bounds via Lifting
Statistics Theory
Makes computer learning more accurate and faster.
A reverse entropy power inequality for i.i.d. log-concave random variables
Probability
Makes math smarter for predicting random events.
Strengthening Han's Fourier Entropy-Influence Inequality via an Information-Theoretic Proof
Information Theory
Makes math rules work for more kinds of problems.