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

We show a connection between sampling and optimization on discrete domains. For a family of distributions μ 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 μ(·). More precisely we show that if (multi-step) down-up random walks have spectral gap at least inverse polynomially large in k, then (multi-step) local search can find max μ(·) within a factor of kO(k). As the main application of our result, we show a simple nearly-optimal kO(k)-factor approximation algorithm for MAP inference on nonsymmetric DPPs. This is the first nontrivial multiplicative approximation for finding the largest size k principal minor of a square (not-necessarily-symmetric) matrix L with L+L^intercalsucceq 0. 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. We further connect exchange inequalities with composable core-sets for optimization, generalizing recent results on composable core-sets for DPP maximization to arbitrary distributions that satisfy either the strongly Rayleigh property or that have a log-concave generating polynomial.