Workshop Details

Spin systems, also known as undirected graphical models, are important tools for modeling joint distributions of discrete random variables. We study the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling for generating samples from the equilibrium distribution of the model (called the Gibbs distribution). In each step, the dynamics picks a single variable uniformly at random and updates it conditional on all other variables. We prove optimal mixing time bounds of the Glauber dynamics in a variety of settings, including hardcore model (weighted independent sets), Ising model, proper colorings, and monomer-dimer model (weighted matchings). To establish our results, we utilize and improve the spectral independence approach of Anari, Liu, and Oveis Gharan (2020) and show optimal mixing time of the Glauber dynamics on bounded-degree graphs when the maximum eigenvalues of associated influence matrices are bounded.

[Video]

I will introduce a notion of expansion for weighted simplicial complexes called entropic independence. This notion is motivated by the desire to obtain tight mixing time bounds for natural discrete Markov chains. As is widely known in Markov Chain analysis, spectral analysis is often lossy (by polynomial factors) when the state space is exponentially large. Instead, Modified Log-Sobolev Inequalities (MLSI), which characterize the rate of entropy decay, are powerful enough to often yield a tight mixing time bound. We show how to obtain entropic independence, and as a consequence, tight MLSI and mixing time bounds, for a range of natural chains/distributions. We recover earlier known results about mixing of basis-exchange walks on matroids, and obtain new tight mixing time bounds for several others: examples include monomer dynamics in monomer-dimer systems, variants of Glauber dynamics in high-temperature Ising models and high-temperature hardcore models, and down-up walks for non-symmetric determinantal point processes. Our framework allows an easy way of lifting the widely successful notion of spectral independence to entropic independence, yielding, in many cases with no extra effort, tight MLSI and mixing times from existing spectral analyses.
Time-permitting, I will discuss an additional application of entropic independence involving analogs of the notion of isotropy and phenomena akin to the KLS conjecture for discrete strongly Rayleigh distributions.
Based on joint works with: Vishesh Jain, Frederic Koehler, Yang P. Liu, Huy Tuan Pham, Thuy-Duong Vuong.

[Video]

Two recent and seemingly-unrelated techniques for proving mixing bounds for Markov chains are: (i) the framework of "Spectral Independence", introduced by Anari, Liu and Oveis Gharan, and its numerous extensions, which have given rise to several breakthroughs in the analysis of mixing times of discrete Markov chains and (ii) the Stochastic Localization technique which has proven useful in establishing mixing and expansion bounds for both log-concave measures and for measures on the discrete hypercube. In this talk, I'll present a framework which aims to both unify and extend those techniques, thus providing an approach that gives bounds for sampling algorithms in both discrete and continuous settings. In its center is the concept of a \`\`localization scheme'' which, to every probability measure on some space $Omega$ (which will usually be either the discrete hypercube or R^n), assigns a martingale of probability measures which \`\`localize'' in space as time evolves. As it turns out, every such scheme can be associated with a Markov chain, and many chains of interest (such as Glauber dynamics) appear naturally in this framework. This viewpoint provides tools for deriving mixing bounds for the dynamics through the analysis of the corresponding localization process. Generalizations of the concept of Spectral Independence naturally arise from our definitions, and in particular we will show how to recover the main theorems in the spectral independence framework via simple martingale arguments (completely bypassing the need to use the theory of high-dimensional expanders). We demonstrate how to apply our machinery towards simple proofs to many mixing bounds in the recent literature. We will briefly discuss some applications, among which are obtaining the first $O(n log n)$ bound for mixing time of the hardcore-model (of arbitrary degree) in the tree-uniqueness regime, under Glauber dynamics and to proving a KL-divergence decay bound for log-concave sampling via the Restricted Gaussian Oracle, which achieves optimal mixing under any $exp(n)$-warm start.
Based on a joint work with Yuansi Chen.

[Video]

Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class Q={q1,…,qn} of distributions, and a sampling access to an unknown target distribution p, the goal is to output a distribution q such that TV(p,q) is close to opt, where opt=mini{TV(p,qi)} and TV(⋅,⋅) denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e.g., in the charming book by Devroye and Lugosi \`00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood.

We derive an optimal 2-approximation learning strategy for the Hypothesis Selection problem, outputting q such that $mathsf{TV}(p,q) leq2 cdot opt + eps$, with a (nearly) optimal sample complexity of~O~(logn/ϵ2). This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT \`19) gave a learner achieving the optimal 2-approximation, but with an exponentially worse sample complexity of O~(n−−√/ϵ2.5), and Yatracos~(Annals of Statistics \`85) gave a learner with optimal sample complexity of O(logn/ϵ2) but with a sub-optimal approximation factor of 3.

Based on work joint with Olivier Bousquet, Klim Efremenko, Gillat Kol, and Shay Moran.

[Video]

I will recall the entropic regularization approach to metrical task systems/k-server. I will then show how to use an *evolving* entropy functional to regularize when the underlying metric space is revealed bit by bit. The punchline is the resolution of layered graph traversal introduced by Papadimitriou and Yannakakis in 1989.

[Video]

Bethe approximation is a standard tool in statistical physics to approximate partition functions of spin models. It works best on locally tree like graphs, in particular, on random regular graphs. I will survey some applications of it including some very recent ones.

[Video]

In a joint work with Mark Rudelson, we present a simple formula to approximate the volume of a bounded polyhedron, defined as the intersection of the non-negative orthant and an affine subspace. The formula requires computing the analytic center of the polyhedron (the point maximizing the sum of the logarithms of the coordinates), which is also the solution to an entropy maximization problem (find the maximum entropy distribution on the non-negative orthant with the expectation in the affine subspace). The formula approximates the volume within a multiplicative factor of gamma^m, where gamma>0 is an absolute constant and m is the codimension of the subspace. Although the result is related to the slicing conjecture, the proof is quite simple, since we deal with a very special case and do not need the conjecture in its whole generality.

[Video]

The maximum-entropy sampling problem (MESP) is to select a subset, of given size s, from a set of n correlated Gaussian random variables, so as to maximize the differential entropy. If C is the covariance matrix, then we are simply seeking to maximize the determinant of an order-s principal submatrix. A key application is for the contraction of an environmental-monitoring network. MESP sits within the intersection of optimization and data science, and so it has attracted a lot of recent attention. The problem is NP-hard, and there have been algorithmic attacks aimed at exact solution of moderate-sized instance for three decades. It is a fascinating problem from the perspective of integer nonlinear optimization, as it does not fit within a framework that is successfully attacked via available general-purpose paradigms. I will give a broad overview of algorithmic work, concentrating on the many useful techniques related to various convex relaxations.

[Video]

Given a polytope P that is a convex hull of a set of 0-1 vectors (usually of constant hamming weight) and a point x in P, one can write x as a distribution over vertices of P of the largest possible entropy. A decade ago, it has been shown that max entropy distributions can be computed/approximated efficiently for a large class 0-1 polytopes. Consequently, max-entropy distributions found numerous applications in (combinatorial) optimization, counting, and (probabilistic) combinatorics over the last decade. Furthermore, this machinery has led to deep connections between distant fields of Math and Theoretical CS namely approximation algorithms, geometry of polynomials, analysis of Markov chains, Operator theory, etc. In this talk I plan to survey some of these applications and connections. I will also propose several unexplored directions for future research.

The spectral notion of high dimensional expansion that goes by the name "local spectral expansion" was instrumental in recent works on approximate counting. However, for state of the art counting results stronger notions of high dimensional  expansion, as spectral independence and entropic independence, had to be considered. The importance in these stronger expansion notions is that the expansion guaranty that they provide does not deteriorate with the sample size (i.e. with the dimension). Alas, these newly investigated stronger notions of high dimensional expansion are known to hold only for dense distributions, like strongly log concave distributions, where the simplicial complexes that describe them have unbounded degree (and there is a short path between every two faces in the simplicial complex). In light of these recent stronger notions of high dimensional expansion, we ask: what is a strong notion of high dimensional expansion that applies also for sparse distributions (as the Ramanujan complexes) that does not deteriorate with the dimension; We give some initial result in this direction.

This presentation is based on joint work with Roy Gotlib