Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems
Abstract Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2023
|
| Online Access: | https://hdl.handle.net/1721.1/152926 |
| _version_ | 1811078280959229952 |
|---|---|
| author | Gu, Yuzhou Polyanskiy, Yury |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Gu, Yuzhou Polyanskiy, Yury |
| author_sort | Gu, Yuzhou |
| collection | MIT |
| description | Abstract
Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant
$$\alpha _2$$
α
2
in the 2-log-Sobolev inequality (2-LSI). In this paper, we obtain the best possible non-linear inequality relating entropy and the Dirichlet form (i.e., p-NLSI,
$$p\ge 1$$
p
≥
1
). As an example, we show
$$\alpha _1 = 1+\frac{1+o(1)}{\log q}$$
α
1
=
1
+
1
+
o
(
1
)
log
q
. Furthermore, p-NLSIs allow us to conclude that for
$$q\ge 3$$
q
≥
3
, distributions that are not a product of identical distributions can have slower speed of convergence to equilibrium, unlike the case
$$q=2$$
q
=
2
. By integrating the 1-NLSI we obtain new strong data processing inequalities (SDPI), which in turn allows us to improve results of Mossel and Peres (Ann Appl Probab 13(3):817–844, 2003) on reconstruction thresholds for Potts models on trees. A special case is the problem of reconstructing color of the root of a q-colored tree given knowledge of colors of all the leaves. We show that to have a non-trivial reconstruction probability the branching number of the tree should be at least
$$\begin{aligned} \frac{\log q}{\log q - \log (q-1)} = (1-o(1))q\log q. \end{aligned}$$
log
q
log
q
-
log
(
q
-
1
)
=
(
1
-
o
(
1
)
)
q
log
q
.
This recovers previous results (of Sly in Commun Math Phys 288(3):943–961, 2009 and Bhatnagar et al. in SIAM J Discrete Math 25(2):809–826, 2011) in (slightly) more generality, but more importantly avoids the need for any coloring-specific arguments. Similarly, we improve the state-of-the-art on the weak recovery threshold for the stochastic block model with q balanced groups, for all
$$q\ge 3$$
q
≥
3
. To further show the power of our method, we prove optimal non-reconstruction results for a broadcasting on trees model with Gaussian kernels, closing a gap left open by Eldan et al. (Combin Probab Comput 31(6):1048–1069, 2022). These improvements advocate information-theoretic methods as a useful complement to the conventional techniques originating from the statistical physics. |
| first_indexed | 2024-09-23T10:57:11Z |
| format | Article |
| id | mit-1721.1/152926 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:57:11Z |
| publishDate | 2023 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1529262024-02-05T18:59:26Z Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems Gu, Yuzhou Polyanskiy, Yury Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abstract Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant $$\alpha _2$$ α 2 in the 2-log-Sobolev inequality (2-LSI). In this paper, we obtain the best possible non-linear inequality relating entropy and the Dirichlet form (i.e., p-NLSI, $$p\ge 1$$ p ≥ 1 ). As an example, we show $$\alpha _1 = 1+\frac{1+o(1)}{\log q}$$ α 1 = 1 + 1 + o ( 1 ) log q . Furthermore, p-NLSIs allow us to conclude that for $$q\ge 3$$ q ≥ 3 , distributions that are not a product of identical distributions can have slower speed of convergence to equilibrium, unlike the case $$q=2$$ q = 2 . By integrating the 1-NLSI we obtain new strong data processing inequalities (SDPI), which in turn allows us to improve results of Mossel and Peres (Ann Appl Probab 13(3):817–844, 2003) on reconstruction thresholds for Potts models on trees. A special case is the problem of reconstructing color of the root of a q-colored tree given knowledge of colors of all the leaves. We show that to have a non-trivial reconstruction probability the branching number of the tree should be at least $$\begin{aligned} \frac{\log q}{\log q - \log (q-1)} = (1-o(1))q\log q. \end{aligned}$$ log q log q - log ( q - 1 ) = ( 1 - o ( 1 ) ) q log q . This recovers previous results (of Sly in Commun Math Phys 288(3):943–961, 2009 and Bhatnagar et al. in SIAM J Discrete Math 25(2):809–826, 2011) in (slightly) more generality, but more importantly avoids the need for any coloring-specific arguments. Similarly, we improve the state-of-the-art on the weak recovery threshold for the stochastic block model with q balanced groups, for all $$q\ge 3$$ q ≥ 3 . To further show the power of our method, we prove optimal non-reconstruction results for a broadcasting on trees model with Gaussian kernels, closing a gap left open by Eldan et al. (Combin Probab Comput 31(6):1048–1069, 2022). These improvements advocate information-theoretic methods as a useful complement to the conventional techniques originating from the statistical physics. 2023-11-09T14:59:25Z 2023-11-09T14:59:25Z 2023-10-20 2023-11-09T04:21:24Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/152926 Gu, Yuzhou and Polyanskiy, Yury. 2023. "Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems." en https://doi.org/10.1007/s00220-023-04851-1 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature application/pdf Springer Berlin Heidelberg Springer Berlin Heidelberg |
| spellingShingle | Gu, Yuzhou Polyanskiy, Yury Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title | Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title_full | Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title_fullStr | Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title_full_unstemmed | Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title_short | Non-linear Log-Sobolev Inequalities for the Potts Semigroup and Applications to Reconstruction Problems |
| title_sort | non linear log sobolev inequalities for the potts semigroup and applications to reconstruction problems |
| url | https://hdl.handle.net/1721.1/152926 |
| work_keys_str_mv | AT guyuzhou nonlinearlogsobolevinequalitiesforthepottssemigroupandapplicationstoreconstructionproblems AT polyanskiyyury nonlinearlogsobolevinequalitiesforthepottssemigroupandapplicationstoreconstructionproblems |