Large deviations, moderate deviations, and the KLS conjecture (Q2210452): Difference between revisions

The authors of the current paper explain that the Kannan-Lovasz-Simonovits (KLS) conjecture has its origin in theoretical computer science [\textit{R. Kannan} et al., Discrete Comput. Geom. 13, No. 3--4, 541--559 (1995; Zbl 0824.52012)]. In that paper, Kannan, Lovasz and Simonovits consider the following setting: given a convex body \(K\) in an \(n\)-dimensional space, assume you cut it in two parts \(K_1\) and \(K_2\), by a surface with an \((n - 1)\)-dimensional surface with measure \(\psi (K) \operatorname{vol} (K_1)\operatorname{vol} (K_2)/ \operatorname{vol} (K)\). The real number \(\psi (K)\) is the isoperimetric coefficient of the convex body \(K\). The problem consists of estimating the value of \(\psi (K)\). Let \(M_1(K)\) denote the average distance of a point of \(K\) from its center of gravity. So, in [loc. cit.], the authors proved the following inequality: \[ \psi (K)\geq \frac{\ln 2}{M_1(K)}. \tag{1} \] Kannan, Lovasz and Simonovits developed estimates on the product \(\operatorname{vol}(K_1)\operatorname{vol}(K_2)\) and finally closed their paper with the celebrated conjecture: one can estimate the isoperimetric coefficient as a function of \(1/\sqrt{\alpha(K)}\), where \(\alpha (K)\) is the largest eigenvalue of the \(n\times n\) matrix of inertia \(A (K)\) about the center of gravity. The authors of the current paper express the KLS conjecture from an algorithmic point of view. The problem is to design an algorithm that efficiently computes the volume of the convex body \(K\). As they say, such an algorithm needs a convex body \(K\) and a quality parameter \(\varepsilon \in (0, \infty)\). A membership oracle, which for each \(x\in\mathbb{R}^n\) can decide whether \(x\) belongs to \(K\), represents the body \(K\). The algorithm returns a number \(V=\operatorname{vol} (K,\varepsilon)\in\mathbb{R}\) such that the following inequality holds: \[ (1-\varepsilon)\operatorname{vol}(K)\leq V\leq (1+\varepsilon) \operatorname{vol}(K). \tag{2} \] And one measures the efficiency of the designed algorithm in terms of the number of arithmetic operations and calls to the membership oracle. The authors then go through an investigation of randomized algorithms. Based on the previous work of Rothaus, Cheeger, Maz'ya, and Ledoux, they state the KLS conjecture in the following form: KLS Conjecture. There is an absolute constant \(C>0\) such that for all \(n\in\mathbb{N}\), every centered random vector \(X\) with a log-concave distribution and any locally Lipschitz function \(f:\mathbb{R}^n\to\mathbb{R}\) such that \(f(X)\) is of finite variance, one has the following property. \[ \operatorname{Var}[f(X)]\leq C \lambda_X^2 \mathbb{E}\left[\Vert X\Vert_2^2\right], \tag{3} \] where \(\lambda_X^2:=\sup_{\theta\in\mathbb{S}^{n-1}}\mathbb{E}\langle X,\theta\rangle^2\). Within this setting, the proof referred to Kannan et al. [loc. cit.] gives a factor \((\mathbb{E}(\Vert X\Vert_2))^2\) instead of \(\lambda_X^2\). Bobkov improved that estimate later. Recently, \textit{Y. Chen} [Geom. Funct. Anal. 31, No. 1, 34--61 (2021; Zbl 1495.52003)] provided a sharper estimate. Here, in the paper under review, the authors explore another interesting connection of the KLS conjecture with large deviations principles, introducing a deeper probabilistic point of view in their analysis. Recall that a sequence \((X_n)_{n\in\mathbb{N}}\) of random vectors in \(d\)-dimensional Euclidean space \(\mathbb{R}^d\) satisfies a \textit{large deviations principle} (LDP) with speed \(s_n\) and rate function \(\mathbb{I}:\mathbb{R}^d\to [0, \infty]\) if \[ - \inf_{x\in A^o} \mathbb{I}(x)\leq\liminf_{n\to\infty}s^{-1}\log P[X \in A]\leq\limsup_{n\to\infty}s^{-1}\log P[X\in A]\leq -\inf_{x\in \bar{A}} \mathbb{I}(x) . \] And, as the authors quote, a \textit{moderate deviations principle} (MDP) is nothing else than an LDP for a differently normalized sequence of random variables. The article includes three main theorems: A, B, C, detailed here below. The first result shows that the KLS conjecture is false if one assumes the LDP under some particular classes of speed sequences \(s_n\). The notation \(x_n = o(y_n)\) means that \(\lim_{n\to\infty}\frac{x_n}{y_n} = 0\) and \(x_n = \omega(y_n)\), means that \(\lim_{n\to\infty}\|{\frac{x_n}{y_n}\|} =+\infty\). In addition, the authors write \(x_n \simeq y_n\) if there exist two absolute constants \(c_1, c_2\) such that \(c_1x_n \leq y_n \leq c_2x_n\). Theorem A (LDPs/MDPs and the KLS conjecture). Let \(1 \leq k_n \leq n\) be a sequence of integers such that \(k_n = \omega(1)\) and let \((\xi_n)_{n=0}^\infty\) be a sequence of isotropic log-concave random vectors in \(\mathbb{R}^{k_n}\). Consider a sequence of random variables \(X =\Vert\xi_n\Vert_2/\sqrt{k_n}\), \(n\in\mathbb{N}\), \(n\) which satisfies the LDP with speed \(s_n\) and rate function \(\mathbb{I}\). Assume that one of the following two conditions is satisfied: \begin{itemize} \item [(a)] \(s_n=o(\sqrt{k_n})\) and \(\mathbb{I}\) is non-singular, i.e., \(\mathbb{I}(x)\not=\mathbb{I}_0(x)=\begin{cases}0 &\text{if }x=1, \\ \infty &\text{otherwise}; \end{cases}\) \item[(b)] \(s_n\simeq \sqrt{k_n} \text{ and } \inf_{t>t_0}\frac{\inf_{x\in (t,\infty)}\mathbb{I}(x)}{t} = 0\) for some absolute constant \(t_0\in (1,\infty)\). \end{itemize} Then the KLS conjecture is false. The second main result of the paper deeply focuses on geometrical aspects, like the class of \(\ell_p^n\)-balls. The authors consider random vectors that arise as orthogonal projections of uniformly distributed random points on the unit ball in \(\mathbb{R}^n\), onto \(k_n\)-dimensional subspaces. Which kind of \(k_n\)-dimensional subspaces? One picks uniformly at random a \(k_n\)-dimensional subspace \(E_n\) of \(\mathbb{R}^n\) according to the Haar measure of the Grassmannnian manifold of all such subspaces. Call \(P_{E_n}\) the projection onto \(E_n\). In addition, one takes a uniformly random vector \(X_n\) in the unit ball of \(\mathbb{R}^n\), assumed to be independent of the choice of \(E_n\). Now, for each \(n\in\mathbb{N}\), consider the random variables \[ \mathcal{Z}_{n,p}=n^{1/p}\Vert P_{E_n}X_n\Vert_2. \] In their second main theorem, the authors explore the MDP for \(\mathcal{Z}_{n,p}\) at scales below \(\sqrt{n}\) that they call \textit{critical scales} \(\sqrt{k_n}\). Theorem B (MDP on the critical scale). Let \(1\leq p < \infty\) and \((k_n)_{n\in\mathbb{N}}\) be a sequence of positive integers \(1 \leq k_n \leq n\) such that \(k_n = \omega (1)\) and \(k_n = o(n)\). Let \(M_p(2) =\frac{p^{2/p}}{3}\frac{\Gamma(1+\frac{3}{p})}{\Gamma(1+\frac{1}{p})}\). Then the following hold: \begin{itemize} \item [(a)] If \(p\geq 2\), then \(k_n^{-1/2}\mathcal{Z}_{n,p}\) satisfies an MDP on \(\mathbb{R}\) with speed \(k_n\) and rate function \[ \mathbb{I}(x)=\begin{cases} \frac{x^2-M_p(2)}{2M_p(2)}-\log \frac{x}{\sqrt{M_p(2)}} \text{ for } &x>0, \\ +\infty &\text{otherwise}. \end{cases} \] \item[(b1)] If \(1\leq p<2\) and \(k_n=o(n^{p/2})\), then \(k_n^{-1/2}\mathcal{Z}_{n,p}\) satisfies an MDP on \(\mathbb{R}\) with speed \(k_n\) and rate function \[ \mathbb{I}(x)=\begin{cases} \frac{x^2-M_p(2)}{2}-\log \frac{x}{\sqrt{M_p(2)}} \text{ for } &x>0, \\ +\infty &\text{otherwise}. \end{cases} \] \item[(b2)] If \(1\leq p<2\) and \(k_n=n^{p/2}\), then \(k_n^{-1/2}\mathcal{Z}_{n,p}\) satisfies an MDP on \(\mathbb{R}\) with speed \(n^{p/2}\) and rate function \[ \mathbb{I}(x)=\begin{cases} \inf_{y\geq m_p}\frac{\left(\frac{x}{y}\right)^2-1}{2}-\log \frac{x}{y}+\frac{1}{p}(y^2-M_p(2))^{p/2} \text{ for } &x>0, \\ +\infty &\text{otherwise}. \end{cases} \] \item [(b3)] If \(1\leq p<2\) and \(k_n=\omega(n^{p/2})\), then \(k_n^{-1/2}\mathcal{Z}_{n,p}\) satisfies an MDP on \(\mathbb{R}\) with speed \(n^{p/2}\) and rate function \[ \mathbb{I}(x)=\begin{cases} \frac{1}{p}(x^2-M_p(2))^{p/2} \text{ for } &x>\sqrt{m_p}, \\ +\infty &\text{otherwise}. \end{cases} \] \end{itemize} The paper finishes with the description of the moderate deviations at subcritical scales \(o(\sqrt{k_n})\), that complement the central limit theorem and the large deviations principle obtained by the authors in a previous publication [\textit{D. Alonso-Gutiérrez} et al., Bernoulli 25, No. 4A, 3139--3174 (2019; Zbl 1431.60011)]. To this end, they change the sequence \(\mathcal{Z}_{n,p}\) into \[ \mathcal{Z}_{n,p}:=n^{1/p}\sqrt{\frac{\Gamma(\frac{1}{p})}{p^{2/p}\Gamma(\frac{3}{p})}}\Vert P_{E_n}X_n\Vert_2-\sqrt{k_n}. \] Theorem C (MDP on subcritical scales). Let \(2\leq p<\infty\) and \((k_n)_{n\in\mathbb{N}}\) be a sequence of integers such that \(1\leq k_n\leq n\) and \(\lim_{n\to\infty}\frac{k_n}{n}=\lambda\in [0,1]\). Assume that \(k_n=\omega (1)\) and that the sequence \((t_n)_{n\in\mathbb{N}}\) of positive real numbers satisfies \(t_n=\omega (1)\), \(t_n=o(\sqrt{k_n})\) and either \(t_n=o(\sqrt{n-k_n})\) or \((n-k_n)=o(\frac{\sqrt{k_n}}{t_n})\). Then the sequence of random variables \(t_n^{-1}\mathcal{Z}_{n,p}\) satisfies an MDP on \(\mathbb{R}\) with speed \(t^2_n\) and rate function \(\mathbb{I}(x)=\alpha_{p,\lambda}x^2\) with constant \(\alpha_{p,\lambda}\) given by \[ \alpha_{p,\lambda}=\frac{2\Gamma(\frac{1}{p})\Gamma(\frac{3}{p})^2}{(2p-\lambda(4+3p))\Gamma(1+\frac{1}{p}))\Gamma(\frac{3}{p})^2+\lambda\Gamma(\frac{1}{p})^2\Gamma(\frac{5}{p})}. \] Section 5 of the paper contains a generalisation of this result. The authors use a remarkable probabilistic representation in their proofs, implemented already in their previous article [loc. cit.]. The reader can appreciate the subtle way in which this probabilistic representation is used to get very sharp estimates in the MDP.