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 $\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(\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
\mu(\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.
