Before revision: Determinantal point processes (DPPs) are widely popular probabilistic models used in machine learning to capture diversity in random subsets of items. While traditional DPPs are defined by a symmetric kernel matrix, recent work has shown a significant increase in the modeling power and applicability of models defined by nonsymmetric kernels, where the model can capture interactions that go beyond diversity. We study the problem of maximum a posteriori (MAP ) inference for determinantal point processes defined by a nonsymmetric positive semidefinite matrix (NDPPs), where the goal is to find the maximum k \times k principal minor of the kernel matrix L . We obtain the first multiplicative approximation guarantee for this problem using local search, a method that has been previously applied to symmetric DPPs.
After revision: 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) principal minor of the kernel matrix L . We obtain the first multiplicative approximation guarantee for this problem using local search, a method that has been previously applied to symmetric DPPs.