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 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 (). 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 () within a factor of k^O(k). As the main application of our result, we show a simple nearly-optimal k^O(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^ 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.

Tasks

Reproductions