Arrow Research search

Author name cluster

Antonio Blanca

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.

8 papers
2 author rows

Possible papers

8

FOCS Conference 2023 Conference Paper

Sampling from the Potts model at low temperatures via Swendsen-Wang dynamics

  • Antonio Blanca
  • Reza Gheissari

Sampling from the q-state ferromagnetic Potts model is a fundamental question in statistical physics, probability theory, and theoretical computer science. On general graphs, this problem is computationally hard, and this hardness holds at arbitrarily low temperatures. At the same time, in recent years, there has been significant progress showing the existence of low-temperature sampling algorithms in various specific families of graphs. Our aim in this paper is to understand the minimal structural properties of general graphs that enable polynomial-time sampling from the q-state ferromagnetic Potts model at low temperatures. We study this problem from the perspective of the widely-used Swendsen-Wang dynamics and the closely related random-cluster dynamics. These are non-local Markov chains that have long been believed to converge rapidly to equilibrium at low temperatures in many graphs. However, the hardness of the sampling problem likely indicates that this is not even the case for all bounded degree graphs. Our results demonstrate that a key graph property behind fast or slow convergence time for these dynamics is whether the independent edge-percolation on the graph admits a strongly supercritical phase. By this, we mean that at large $p\lt 1$, it has a large linear-sized component, and the graph complement of that component is comprised of only small components Specifically, we prove that such a condition implies fast mixing of the Swendsen-Wang and random-cluster dynamics on two general families of bounded-degree graphs: (a) graphs of at most stretched-exponential volume growth and (b) locally treelike graphs. In the other direction, we show that, even among graphs in those families, these Markov chains can converge exponentially slowly at arbitrarily low temperatures if the edge-percolation condition does not hold. In the process, we develop new tools for the analysis of non-local Markov chains, including a framework to bound the speed of disagreement propagation in the presence of long-range correlations, an understanding of spatial mixing properties on trees with random boundary conditions, and an analysis of burn-in phases at low temperatures.

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

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

SODA Conference 2016 Conference Paper

Random-Cluster Dynamics in ℤ 2

  • Antonio Blanca
  • Alistair Sinclair

The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and electrical networks, but its dynamics have so far largely resisted analysis. In this paper we analyze the Glauber dynamics of the random-cluster model in the canonical case where the underlying graph is an n × n box in the Cartesian lattice ℤ 2. Our main result is a O ( n 2 log n ) upper bound for the mixing time at all values of the model parameter p except the critical point p = p c ( q ), and for all values of the second model parameter q ≥ 1. We also provide a matching lower bound proving that our result is tight. Our analysis takes as its starting point the recent breakthrough by Beffara and Duminil-Copin on the location of the random-cluster phase transition in ℤ 2. It is reminiscent of similar results for spin systems such as the Ising and Potts models, but requires the reworking of several standard tools in the context of the random-cluster model, which is not a spin system in the usual sense.

Details