From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization

Abstract

We show a connection between sampling and optimization on discrete domains. For a family of distributions mu defined on size k subsets of a ground set of elements that is closed under external fields, we show that rapid mixing of natural local random walks implies the existence of simple approximation algorithms to find max mu(.). More precisely we show that if t-step down-up random walks have spectral gap at least inverse polynomially large, then t-step local search can find max mu(.) within a factor of k^O(k). As the main application of our result, we show that 2-step local search achieves a nearly-optimal k^O(k)-factor approximation for MAP inference on nonsymmetric k-DPPs. This is the first nontrivial multiplicative approximation algorithm for this problem. We establish the connection between sampling and optimization by showing that an exchange inequality, a concept rooted in discrete convex analysis, can be derived from fast mixing of local random walks. Based on joint work with Nima Anari.