Displacement convexity of entropy and related inequalities on graphs (Q466893): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(7 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Cyril Roberto / rank | |||
Property / author | |||
Property / author: Paul-Marie Samson / rank | |||
Property / author | |||
Property / author: Cyril Roberto / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Paul-Marie Samson / rank | |||
Normal rank | |||
Property / review text | |||
In recent years, there has been a great interest in developing a notion of Ricci curvature in the setting of discrete spaces, i.e., finite graphs or finite Markov chains. A fruitful direction has been one where Ricci curvature is defined via convexity properties of the relative entropy regarded as a function on the space of probability measures equipped with a \(L_p\)-Wasserstein metric or a related metric. The study of convexity properties of relative entropy is important because of its connection to several geometric and function inequalities, and several approaches to extend this theory to discrete settings have been proposed. One which uses a pseudo Wasserstein metric was developed in [\textit{J. Maas}, J. Funct. Anal. 261, No. 8, 2250--2292 (2011; Zbl 1237.60058)] and [\textit{M. Erbar} and \textit{J. Maas}, Arch. Ration. Mech. Anal. 206, No. 3, 997--1038 (2012; Zbl 1256.53028)]. Consider the discrete hypercube \(X = \{0,1\}^n\), and let \(\nu\) be the uniform probability measure on \(X\). \textit{Y. Ollivier} and \textit{C. Villani} [SIAM J. Discrete Math. 26, No. 3, 983--996 (2012; Zbl 1267.52010)] proved that, for any probability measures \(\mu_0\) and \(\mu_1\) in \(X\), one can construct a probability measure \(\mu_{1/2}\) on the set of midpoints of the supports of \(\mu_0\) and \(\mu_1\) such that \[ H(\mu_{1/2}|\nu) \leq \frac{1}{2}\, H(\mu_0|\nu) + \frac{1}{2}\, H(\mu_1|\nu) - \frac{1}{16n}\, W_1(\mu_0,\mu_1)^2, \] where \(H(\cdot|\nu)\) denotes relative entropy, and \(W_1\) denotes the \(L_1\)-Wasserstein distance. In this article, the authors propose another interpolation between probability measures and derive a similar inequality which holds in a more general setting. More precisely, let \(G\) be a finite graph with vertex set \(V\). For any two vertices \(x\) and \(y\), the authors define a path \(\mu_t^{x,y}\) between the corresponding delta measures \(\delta_x\) and \(\delta_y\) based on a binomial interpolation. The definition of \(\mu_t^{x,y}\) includes the contribution of all the geodesics from \(x\) to \(y\). From this, they construct a path between any two probability measures on \(V\). That is, let \(\mu_0\) and \(\mu_1\) be any two probability measures on \(V\). For any coupling \(\pi\) of \(\mu_0\) and \(\mu_1\), the authors define a path \(\mu_t^{\pi}\) from \(\mu_0\) to \(\mu_1\) by \[ \mu_t^{\pi} (\cdot) = \sum_{(x,y)\in V^2} \pi (x,y) \mu_t^{x,y}(\cdot) ,\quad \text{for all } t \in [0,1]. \] Using this new notion the authors derive a displacement convexity of entropy inequality with respect to the \(L_1\)-Wasserstein-metric on the complete graph and products of complete graphs, and from this result they derive several important inequalities, i.e., a discrete version of the Prékopa-Leindler type inequalities, and HWI type inequalities on graphs. In particular, for the discrete hypercube, they prove the following result: Theorem. Let \(\mu\) be a probability on \(\{0,1\}\), and denote by \(\mu^{\otimes n}\) its \(n\)-fold product on \(X\). Then, for any two probability measures \(\mu_0\) and \(\mu_1\) on \(X\), there exists a coupling \(\pi\) of \(\mu_0\) and \(\mu_1\) such that, for all \(t\in [0,1]\), \[ H(\mu_t^{\pi}|\mu^{\otimes n}) \leq (1-t) H (\mu_0|\mu^{\otimes n}) + t H(\mu_1| \mu^{\otimes n}) - \frac{2t(1-t)}{n} W_1(\mu_0,\mu_1)^2. \] In the introduction, the authors provide an overview of known results with extensive references for both continuous and discrete settings. A related work which uses another type of binomial interpolation can be found in [\textit{E. Hillion}, Potential Anal. 41, No. 3, 679--698 (2014; Zbl 1305.60014)]. | |||
Property / review text: In recent years, there has been a great interest in developing a notion of Ricci curvature in the setting of discrete spaces, i.e., finite graphs or finite Markov chains. A fruitful direction has been one where Ricci curvature is defined via convexity properties of the relative entropy regarded as a function on the space of probability measures equipped with a \(L_p\)-Wasserstein metric or a related metric. The study of convexity properties of relative entropy is important because of its connection to several geometric and function inequalities, and several approaches to extend this theory to discrete settings have been proposed. One which uses a pseudo Wasserstein metric was developed in [\textit{J. Maas}, J. Funct. Anal. 261, No. 8, 2250--2292 (2011; Zbl 1237.60058)] and [\textit{M. Erbar} and \textit{J. Maas}, Arch. Ration. Mech. Anal. 206, No. 3, 997--1038 (2012; Zbl 1256.53028)]. Consider the discrete hypercube \(X = \{0,1\}^n\), and let \(\nu\) be the uniform probability measure on \(X\). \textit{Y. Ollivier} and \textit{C. Villani} [SIAM J. Discrete Math. 26, No. 3, 983--996 (2012; Zbl 1267.52010)] proved that, for any probability measures \(\mu_0\) and \(\mu_1\) in \(X\), one can construct a probability measure \(\mu_{1/2}\) on the set of midpoints of the supports of \(\mu_0\) and \(\mu_1\) such that \[ H(\mu_{1/2}|\nu) \leq \frac{1}{2}\, H(\mu_0|\nu) + \frac{1}{2}\, H(\mu_1|\nu) - \frac{1}{16n}\, W_1(\mu_0,\mu_1)^2, \] where \(H(\cdot|\nu)\) denotes relative entropy, and \(W_1\) denotes the \(L_1\)-Wasserstein distance. In this article, the authors propose another interpolation between probability measures and derive a similar inequality which holds in a more general setting. More precisely, let \(G\) be a finite graph with vertex set \(V\). For any two vertices \(x\) and \(y\), the authors define a path \(\mu_t^{x,y}\) between the corresponding delta measures \(\delta_x\) and \(\delta_y\) based on a binomial interpolation. The definition of \(\mu_t^{x,y}\) includes the contribution of all the geodesics from \(x\) to \(y\). From this, they construct a path between any two probability measures on \(V\). That is, let \(\mu_0\) and \(\mu_1\) be any two probability measures on \(V\). For any coupling \(\pi\) of \(\mu_0\) and \(\mu_1\), the authors define a path \(\mu_t^{\pi}\) from \(\mu_0\) to \(\mu_1\) by \[ \mu_t^{\pi} (\cdot) = \sum_{(x,y)\in V^2} \pi (x,y) \mu_t^{x,y}(\cdot) ,\quad \text{for all } t \in [0,1]. \] Using this new notion the authors derive a displacement convexity of entropy inequality with respect to the \(L_1\)-Wasserstein-metric on the complete graph and products of complete graphs, and from this result they derive several important inequalities, i.e., a discrete version of the Prékopa-Leindler type inequalities, and HWI type inequalities on graphs. In particular, for the discrete hypercube, they prove the following result: Theorem. Let \(\mu\) be a probability on \(\{0,1\}\), and denote by \(\mu^{\otimes n}\) its \(n\)-fold product on \(X\). Then, for any two probability measures \(\mu_0\) and \(\mu_1\) on \(X\), there exists a coupling \(\pi\) of \(\mu_0\) and \(\mu_1\) such that, for all \(t\in [0,1]\), \[ H(\mu_t^{\pi}|\mu^{\otimes n}) \leq (1-t) H (\mu_0|\mu^{\otimes n}) + t H(\mu_1| \mu^{\otimes n}) - \frac{2t(1-t)}{n} W_1(\mu_0,\mu_1)^2. \] In the introduction, the authors provide an overview of known results with extensive references for both continuous and discrete settings. A related work which uses another type of binomial interpolation can be found in [\textit{E. Hillion}, Potential Anal. 41, No. 3, 679--698 (2014; Zbl 1305.60014)]. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Italo Simonelli / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 60E15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 39A12 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 32F32 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6363137 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
relative entropy | |||
Property / zbMATH Keywords: relative entropy / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
displacement convexity | |||
Property / zbMATH Keywords: displacement convexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
transport inequalities | |||
Property / zbMATH Keywords: transport inequalities / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
modified logarithmic-Sobolev inequalities | |||
Property / zbMATH Keywords: modified logarithmic-Sobolev inequalities / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Ricci curvature | |||
Property / zbMATH Keywords: Ricci curvature / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2076868927 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1207.5116 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q2734149 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4309937 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modified logarithmic Sobolev inequalities in discrete settings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Mass transportation and rough curvature bounds for discrete spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex entropy decay via the Bochner-Bakry-Emery approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Riemannian interpolation inequality à la Borell, Brascamp and Lieb / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5539510 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Entropy inequalities for unbounded spin systems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Information inequalities and concentration of measure / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gradient flows of the entropy for jump processes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ricci curvature of finite Markov chains via convexity of the entropy / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Exponential decay of entropy in the random transposition and Bernoulli-Laplace models / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gromov--Hausdorff Convergence of Discrete Transportation Metrics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Modified logarithmic Sobolev inequalities for some models of random walk / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Logarithmic Sobolev Inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Gradient flows of the entropy for finite Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contraction of measures on graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ricci curvature and eigenvalue estimate on locally finite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Log-concavity and the maximum entropy property of the Poisson distribution / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Contributions to the theory of convex bodies / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Representation formula for the entropy and functional inequalities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5670868 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A convexity principle for interacting gases / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ricci curvature for metric-measure spaces via optimal transport / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A measure concentration inequality for contracting Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ricci curvature of Markov chains on metric spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Monotonicity of the extremal functions for one-dimensional inequalities of logarithmic Sobolev type / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geodesic convexity of the relative entropy in reversible Markov chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Curved Brunn--Minkowski Inequality on the Discrete Hypercube, Or: What Is the Ricci Curvature of the Discrete Hypercube? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5329487 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5645216 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5682159 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transport inequalities, gradient estimates, entropy and Ricci curvature / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Remarks on a Multivariate Transformation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4358811 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Concentration on the Discrete Torus Using Transportation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Concentration of measure inequalities for Markov chains and \(\Phi\)-mixing processes. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Infimum-convolution description of concentration properties of product probability measures, with applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex functionals of probability measures and nonlinear diffusions on manifolds / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the geometry of metric measure spaces. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the geometry of metric measure spaces. II / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4805362 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Optimal Transport / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:27, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Displacement convexity of entropy and related inequalities on graphs |
scientific article |
Statements
Displacement convexity of entropy and related inequalities on graphs (English)
0 references
31 October 2014
0 references
In recent years, there has been a great interest in developing a notion of Ricci curvature in the setting of discrete spaces, i.e., finite graphs or finite Markov chains. A fruitful direction has been one where Ricci curvature is defined via convexity properties of the relative entropy regarded as a function on the space of probability measures equipped with a \(L_p\)-Wasserstein metric or a related metric. The study of convexity properties of relative entropy is important because of its connection to several geometric and function inequalities, and several approaches to extend this theory to discrete settings have been proposed. One which uses a pseudo Wasserstein metric was developed in [\textit{J. Maas}, J. Funct. Anal. 261, No. 8, 2250--2292 (2011; Zbl 1237.60058)] and [\textit{M. Erbar} and \textit{J. Maas}, Arch. Ration. Mech. Anal. 206, No. 3, 997--1038 (2012; Zbl 1256.53028)]. Consider the discrete hypercube \(X = \{0,1\}^n\), and let \(\nu\) be the uniform probability measure on \(X\). \textit{Y. Ollivier} and \textit{C. Villani} [SIAM J. Discrete Math. 26, No. 3, 983--996 (2012; Zbl 1267.52010)] proved that, for any probability measures \(\mu_0\) and \(\mu_1\) in \(X\), one can construct a probability measure \(\mu_{1/2}\) on the set of midpoints of the supports of \(\mu_0\) and \(\mu_1\) such that \[ H(\mu_{1/2}|\nu) \leq \frac{1}{2}\, H(\mu_0|\nu) + \frac{1}{2}\, H(\mu_1|\nu) - \frac{1}{16n}\, W_1(\mu_0,\mu_1)^2, \] where \(H(\cdot|\nu)\) denotes relative entropy, and \(W_1\) denotes the \(L_1\)-Wasserstein distance. In this article, the authors propose another interpolation between probability measures and derive a similar inequality which holds in a more general setting. More precisely, let \(G\) be a finite graph with vertex set \(V\). For any two vertices \(x\) and \(y\), the authors define a path \(\mu_t^{x,y}\) between the corresponding delta measures \(\delta_x\) and \(\delta_y\) based on a binomial interpolation. The definition of \(\mu_t^{x,y}\) includes the contribution of all the geodesics from \(x\) to \(y\). From this, they construct a path between any two probability measures on \(V\). That is, let \(\mu_0\) and \(\mu_1\) be any two probability measures on \(V\). For any coupling \(\pi\) of \(\mu_0\) and \(\mu_1\), the authors define a path \(\mu_t^{\pi}\) from \(\mu_0\) to \(\mu_1\) by \[ \mu_t^{\pi} (\cdot) = \sum_{(x,y)\in V^2} \pi (x,y) \mu_t^{x,y}(\cdot) ,\quad \text{for all } t \in [0,1]. \] Using this new notion the authors derive a displacement convexity of entropy inequality with respect to the \(L_1\)-Wasserstein-metric on the complete graph and products of complete graphs, and from this result they derive several important inequalities, i.e., a discrete version of the Prékopa-Leindler type inequalities, and HWI type inequalities on graphs. In particular, for the discrete hypercube, they prove the following result: Theorem. Let \(\mu\) be a probability on \(\{0,1\}\), and denote by \(\mu^{\otimes n}\) its \(n\)-fold product on \(X\). Then, for any two probability measures \(\mu_0\) and \(\mu_1\) on \(X\), there exists a coupling \(\pi\) of \(\mu_0\) and \(\mu_1\) such that, for all \(t\in [0,1]\), \[ H(\mu_t^{\pi}|\mu^{\otimes n}) \leq (1-t) H (\mu_0|\mu^{\otimes n}) + t H(\mu_1| \mu^{\otimes n}) - \frac{2t(1-t)}{n} W_1(\mu_0,\mu_1)^2. \] In the introduction, the authors provide an overview of known results with extensive references for both continuous and discrete settings. A related work which uses another type of binomial interpolation can be found in [\textit{E. Hillion}, Potential Anal. 41, No. 3, 679--698 (2014; Zbl 1305.60014)].
0 references
relative entropy
0 references
displacement convexity
0 references
transport inequalities
0 references
modified logarithmic-Sobolev inequalities
0 references
Ricci curvature
0 references
0 references
0 references
0 references
0 references