Conference Agenda

Overview and details of the sessions of this conference. Please select a date or location to show only sessions at that day or location. Please select a single session for detailed view (with abstracts and downloads if available).

 
Session Overview
Session
MS198: Positive and negative association
Time:
Friday, 12/Jul/2019:
10:00am - 12:00pm

Location: Unitobler, F-121
52 seats, 100m^2

Presentations
10:00am - 12:00pm

Positive and negative association

Chair(s): Caroline Uhler (MIT), Cynthia Vinzant (North Carolina State)

Positive and negative association form strong and useful conditions on probability distributions that appear in several applications. Algebraic and combinatorial methods have led to methods for understanding and sampling from important classes of these distributions. This session aims to explore some of the recent breakthroughs and applications of positive and negative association.

 

(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)

 

Negative dependence and sampling

Stephanie Jegelka
MIT

Negative dependence occurs in various forms in probability and machine learning. A prominent example with applications in both probabilistic modeling and randomized algorithms are Determinantal Point Processes (DPPs). DPPs belong to the class of Strongly Rayleigh measures that are characterized by real stable polynomials and exhibit strong notions of negative dependence. For practical applications, it is important that procedures such as sampling can be performed efficiently; recent work suggests that negative dependence can enable exactly that. In this talk, I will summarize selected applications of Determinantal Point Processes and other Strongly Rayleigh measures, and then show results on fast mixing of Markov chains for those measures. Several of these results rely on the connections to real stable polynomials.

 

Log-concave polynomials: Polynomials that a drunkard can (almost) evaluate

Nima Anari1, Kuikui Liu2, Shayan Oveis Gharan2, Cynthia Vinzant3
1Stanford, 2U. Washington, 3North Carolina State

A central question in algorithm design is what kind of distributions can we sample from efficiently? On the continuous side, uniform distributions over convex sets and more generally log-concave distributions constitute the main tractable class. We will build a parallel theory on the discrete side, that yields tractability for important discrete distributions such as uniform distributions over matroids, generalizations of determinantal point processes, and some regime of the random cluster model.

The hammer enabling these algorithmic advances is the introduction and the study of a class of polynomials, that we call completely log-concave. Sampling from discrete distributions becomes equivalent to approximately evaluating associated multivariate polynomials, and we will see how we can use very simple random walks to perform both tasks. This is based on joint work with Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.

 

Total positivity in structured binary distributions

Steffen Lauritzen1, Caroline Uhler2, Piotr Zwiernik3
1University of Copenhagen, 2MIT, 3Universitat Pompeu Fabra

We study estimation in totally positive binary distributions, in particular quadratic exponential families of these. Using results from convex optimization we show how the restriction of total positivity induces conditional independence restrictions on the estimated distributions. Also, we give necessary and sufficient conditions for the maximum likelihood estimate to exist within the corresponding exponential family and develop a globally convergent algorithm for its computation. This represents joint work with Caroline Uhler and Piotr Zwiernik.

 

Geometric problems in non-parametric statistics

Elina Robeva1, Bernd Sturmfels2, Ngoc Tran3, Caroline Uhler1
1MIT, 2MPI Leipzig, UC Berkeley, 3U Texas, Austin

We examine maximum likelihood estimation for probability densities that are both log-concave and totally positive. The solution to this optimization problem is intriguing. One ingredient is the study of convex polytopes that are closed under coordinate-wise maximum and minimum. This is joint work with Elina Robeva, Ngoc Tran, and Caroline Uhler.