























We establish analogs of Cheeger's inequality for probability measures with heavy tails. As one of the principal applications, suppose $λ> 3$ and define the (Pareto) probability measure $μ_λ$ on $[1,\infty)$ by $dμ_λ(x) = (λ- 1) x^{-λ}$. Let $μ_λ^n$ denote the product measure of $μ_λ$ on $\mathbb{R}^n$. Then, for any $1$-Lipschitz function (with respect to the Euclidean distance) $f : \mathbb{R}^n \to \mathbb{R}$, we obtain the variance bound $\operatorname{Var}_{μ_λ^n}(f) \le C(λ)\, n^{\frac{2}{λ- 1}}$, where $C(λ)$ is an explicit constant depending only on $λ$. This improves upon the existing bound $\operatorname{Var}_{μ_λ^n}(f) = O(n)$ derived from the Efron--Stein inequality. Moreover, this bound is asymptotically tight when considering the $1$-Lipschitz function $f(x) = |x|_{\infty}$ corresponding to the $L^{\infty}$ norm. In probabilistic terms, suppose $X_1, \dots, X_n$ are i.i.d.\ random variables with distribution $μ_λ$. Then, for any $1$-Lipschitz function $f$, we have $\operatorname{Var}(f(X_1, \dots, X_n)) \le C'(λ)\operatorname{Var}(\max\{X_1, \dots, X_n\}) = Θ\!\left(n^{\frac{2}{λ- 1}}\right)$, where $C'(λ)$ is another explicit constant depending only on $λ$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。