From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization
This provides a theoretical framework for optimization in discrete settings, with applications to determinant maximization, but it is incremental as it builds on existing concepts like exchange inequalities and composable core-sets.
The paper tackles the problem of connecting sampling and optimization on discrete domains, showing that rapid mixing of local random walks implies simple approximation algorithms for maximizing certain distributions, resulting in a nearly-optimal k^{O(k)}-factor approximation for MAP inference on nonsymmetric DPPs.
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 μ(\cdot)$. 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 μ(\cdot)$ 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^\intercal\succeq 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.