Arrow Research search

Author name cluster

Zongchen Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

FOCS Conference 2025 Conference Paper

Rapid Mixing on Random Regular Graphs beyond Uniqueness

  • Xiaoyu Chen
  • Zejia Chen
  • Zongchen Chen
  • Yitong Yin
  • Xinyuan Zhang

The hardcore model is a fundamental probabilistic model extensively studied in statistical physics, probability theory, and computer science. It defines a Gibbs distribution over independent sets of a given graph, parameterized by a vertex activity λ > 0. For graphs of maximum degree ∆, a well-known computational phase transition occurs at the tree-uniqueness threshold ${\lambda _c}(\Delta ) = \frac{{{{(\Delta - 1)}^{\Delta - 1}}}}{{{{(\Delta - 2)}^\Delta }}}$, where the mixing behavior of the Glauber dynamics (a simple Markov chain) undergoes a sharp transition: it mixes in nearly linear time for λ c (∆), in polynomial but super-linear time at λ = λ c (∆), and experiences exponential slowdown for λ > λ c (∆). It is conjectured that random regular graphs exhibit different mixing behavior, with the slowdown occurring far beyond the uniqueness threshold. We confirm this conjecture by showing that, for the hardcore model on random ∆-regular graphs, the Glauber dynamics mixes rapidly with high probability when $\lambda = O\left( {1/\sqrt \Delta } \right)$, which is significantly beyond the uniqueness threshold λ c (∆) ≈ e/∆. Our result establishes a sharp distinction between the hardcore model on worst-case and beyond-worst-case instances, showing that the worst-case and average-case complexities of sampling and counting are fundamentally different. This result of rapid mixing on random instances follows from a new criterion we establish for rapid mixing of Glauber dynamics for any distribution supported on a downward closed set family. Our criterion is simple, general, and easy to check. In addition to proving new mixing conditions for the hardcore model, we also establish improved mixing time bounds for sampling uniform matchings or b-matchings on graphs, the random cluster model on matroids with q ∈ [0, 1), and the determinantal point process. Our proof of this new criterion for rapid mixing combines and generalizes several recent tools in a novel way, including a trickle-down theorem for field dynamics, spectral/entropic stability, and a new comparison result between field dynamics and Glauber dynamics.

Details

SODA Conference 2024 Conference Paper

Fast Sampling of b -Matchings and b -Edge Covers

  • Zongchen Chen
  • Yuzhou Gu

For an integer b ≥ 1, a b -matching (resp. b -edge cover) of a graph G = ( V, E ) is a subset S ⊆ E of edges such that every vertex is incident with at most (resp. at least) b edges from S. We prove that for any b ≥ 1 the simple Glauber dynamics for sampling (weighted) b -matchings and b -edge covers mixes in O ( n log n ) time on all n -vertex bounded-degree graphs. This significantly improves upon previous results which have worse running time and only work for b -matchings with b ≤ 7 and for b -edge covers with b ≤ 2. More generally, we prove spectral independence for a broad class of binary symmetric Holant problems with log-concave signatures, including b -matchings, b -edge covers, and antiferromagnetic 2-spin edge models. We hence deduce optimal mixing time of the Glauber dynamics from spectral independence. The core of our proof is a recursive coupling inspired by [CZ23] which upper bounds the Wasserstein W 1 distance between distributions under different pinnings. Using a similar method, we also obtain the optimal O ( n log n ) mixing time of the Glauber dynamics for the hardcore model on n-vertex bounded-degree claw-free graphs, for any fugacity λ. This improves over previous works which have at least cubic dependence on n.

Details

SODA Conference 2023 Conference Paper

Almost-Linear Planted Cliques Elude the Metropolis Process

  • Zongchen Chen
  • Elchanan Mossel
  • Ilias Zadik

A seminal work of Jerrum (1992) showed that large cliques elude the Metropolis process. More specifically, Jerrum showed that the Metropolis algorithm cannot find a clique of size k = Θ( n α ) for α ∈ (0, 1/2), which is planted in the Erdős-Rényi random graph G(n, 1/2), in polynomial time. Information theoretically it is possible to find such planted cliques as soon as k ≥ (2 + ε) log n. Since the work of Jerrum, the computational problem of finding a planted clique in G(n, 1/2) was studied extensively and many polynomial time algorithms were shown to find the planted clique if it is of size, while no polynomial-time algorithm is known to work when. The computational problem of finding a planted clique of size is now widely considered as a foundational problem in the study of computational-statistical gaps. Notably, the first evidence of the problem's algorithmic hardness is commonly attributed to the result of Jerrum from 1992. In this paper we revisit the original Metropolis algorithm suggested by Jerrum. Interestingly, we find that the Metropolis algorithm actually fails to recover a planted clique of size k = Θ( n α ) for any constant α ∈ (0, 1), unlike many other efficient algorithms that succeed when α > 1/2. Moreover, we strengthen Jerrum's results in a number of other ways including: • Like many results in the MCMC literature, the result of Jerrum shows that there exists a starting state (which may depend on the instance) for which the Metropolis algorithm fails to find the planted clique in polynomial time. For a wide range of temperatures, we show that the algorithm fails when started at the most natural initial state, which is the empty clique. This answers an open problem stated in Jerrum (1992). We highlight that it is rather rare to be able to show the failure of a Markov chain starting from a specific state, which is arguably an important missing piece in the Markov chain literature. • We show that the simulated tempering version of the Metropolis algorithm, a more sophisticated temperature-exchange variant of it, also fails at the same regime of parameters. Our results substantially extend Jerrum's result. Furthermore, they confirm recent predictions by Gamarnik and Zadik (2019) and Angelini, Fachin, de Feo (2021). * The full version of the paper can be accessed at https: //arxiv. org/abs/2204. 01911

Details

FOCS Conference 2023 Conference Paper

Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

  • Zongchen Chen
  • Kuikui Liu
  • Nitya Mani
  • Ankur Moitra

Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q-colorings on a $\Delta$ regular tree exhibits SSM whenever $q \geq \Delta+1$. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q-colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1)For any $\Delta \geq 3$, SSM holds for random q-colorings on trees of maximum degree $\Delta$ whenever $q \geq \Delta+3$. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires $q \geq 1. 59 \Delta+\gamma^{*}$ for an absolute constant $\gamma^{*}\gt0$. (2)For any $\Delta \geq 3$ and $g=\Omega_{\Delta}(1)$, we establish optimal mixing of the Glauber dynamics for q-colorings on graphs of maximum degree $\Delta$ and girth g whenever $q \geq \Delta+3$. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees.

Details

SODA Conference 2022 Conference Paper

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region

  • Zongchen Chen
  • Andreas Galanis
  • Daniel Stefankovic
  • Eric Vigoda

We give an FPRAS for counting q -colorings for even on almost every Δ-regular bipartite graph. This improves significantly upon the previous best bound of by Jenssen, Keevash, and Perkins (SODA'19). Analogously, for the hard-core model on independentsets weighted by λ > 0, we present an FPRAS for estimating the partition function when, which improves upon previous results by an Ω(log Δ) factor. Our results for the colorings and hard-core models follow from a general result that applies to arbitrary spin systems. Our main contribution is to show how to elevate probabilistic/analytic bounds on the marginal probabilities for the typical structure of phases on random bipartite regular graphs into efficient algorithms, using the polymer method. We further show evidence that our results for colorings and independent sets are within a constant factor of best possible using current polymer-method approaches.

Details

JMLR Journal 2021 Journal Article

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models

  • Antonio Blanca
  • Zongchen Chen
  • Daniel Štefankovič
  • Eric Vigoda

We study the identity testing problem for restricted Boltzmann machines (RBMs), and more generally, for undirected graphical models. In this problem, given sample access to the Gibbs distribution corresponding to an unknown or hidden model $M^*$ and given an explicit model $M$, the goal is to distinguish if either $M = M^*$ or if the models are (statistically) far apart. We establish the computational hardness of identity testing for RBMs (i.e., mixed Ising models on bipartite graphs), even when there are no latent variables or an external field. Specifically, we show that unless $RP=NP$, there is no polynomial-time identity testing algorithm for RBMs when $\beta d=\omega(\log{n})$, where $d$ is the maximum degree of the visible graph and $\beta$ is the largest edge weight (in absolute value); when $\beta d =O(\log{n})$ there is an efficient identity testing algorithm that utilizes the structure learning algorithm of Klivans and Meka (2017). We prove similar lower bounds for purely ferromagnetic RBMs with inconsistent external fields and for the ferromagnetic Potts model. To prove our results, we introduce a novel methodology to reduce the corresponding approximate counting problem to testing utilizing the phase transition exhibited by these models. [abs] [ pdf ][ bib ] &copy JMLR 2021. ( edit, beta )

PDF Details

SODA Conference 2021 Conference Paper

Rapid Mixing for Colorings via Spectral Independence

  • Zongchen Chen
  • Andreas Galanis
  • Daniel Stefankovic
  • Eric Vigoda

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let α ∗ ≈ 1. 763 denote the solution to exp(1/ x ) = x and let α > α ∗. We prove that, for any triangle-free graph G = ( V, E ) with maximum degree Δ, for all q ≥ α Δ + 1, the mixing time of the Glauber dynamics for q -colorings is polynomial in n = |V|, with the exponent of the polynomial independent of Δ and q. In comparison, previous approximate counting results for colorings held for a similar range of q (asymptotically in Δ) but with larger girth requirement or with a running time where the polynomial exponent depended on Δ and q (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.

Details

FOCS Conference 2021 Conference Paper

Spectral Independence via Stability and Applications to Holant-Type Problems

  • Zongchen Chen
  • Kuikui Liu
  • Eric Vigoda

This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then spectral independence holds at $\lambda$. As a consequence, for Holant-type problems (e. g. , spin systems) on bounded-degree graphs, we obtain optimal $O(n\ \text{log}\ n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvi-nok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i. e. , edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O$ ( $n$ log n) sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O$ ( $n$ log n) sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.

Details

JMLR Journal 2020 Journal Article

Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models

  • Ivona Bezáková
  • Antonio Blanca
  • Zongchen Chen
  • Daniel Štefankovič
  • Eric Vigoda

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless $RP=NP$. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

PDF Details

FOCS Conference 2020 Conference Paper

Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction

  • Zongchen Chen
  • Kuikui Liu
  • Eric Vigoda

For general antiferromagnetic 2-spin systems, including the hardcore model on weighted independent sets and the antiferromagnetic Ising model, there is an FPTAS for the partition function on graphs of maximum degree Δ when the infinite regular tree lies in the uniqueness region by Li et al. (2013). Moreover, in the tree non-uniqueness region, Sly (2010) showed that there is no FPRAS to estimate the partition function unless NP=RP. The algorithmic results follow from the correlation decay approach due to Weitz (2006) or the polynomial interpolation approach developed by Barvinok (2016). However the running time is only polynomial for constant Δ. For the hardcore model, recent work of Anari et al. (2020) establishes rapid mixing of the simple single-site Markov chain known as the Glauber dynamics in the tree uniqueness region. Our work simplifies their analysis of the Glauber dynamics by considering the total pairwise influence of a fixed vertex v on other vertices, as opposed to the total influence of other vertices on v, thereby extending their work to all 2-spin models and improving the mixing time. More importantly our proof ties together the three disparate algorithmic approaches: we show that contraction of the so-called tree recursions with a suitable potential function, which is the primary technique for establishing efficiency of Weitz's correlation decay approach and Barvinok's polynomial interpolation approach, also establishes rapid mixing of the Glauber dynamics. We emphasize that this connection holds for all 2-spin models (both antiferromagnetic and ferromagnetic), and existing proofs for the correlation decay or polynomial interpolation approach immediately imply rapid mixing of the Glauber dynamics. Our proof utilizes that the graph partition function is a divisor of the partition function for Weitz's self-avoiding walk tree. This fact leads to new tools for the analysis of the influence of vertices, and may be of independent interest for the study of complex zeros.

Details