From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization
From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Nima Anari;T. Vuong
中科院分区：
文献类型：
--
作者：
Nima Anari;T. Vuong
我们在离散域上显示了采样和优化之间的连接。对于一个分布的家族$ \ mu $定义的尺寸$ k $子集的一组地面元素的子集，我们表明，自然局部随机步行的快速混合意味着存在简单的近似算法，可以找到$ \ \ \ \ \ \ \最大\ mu（\ cdot）$。更确切地说，如果（多步）向上随机步道（至少在$ k $中具有相反的多项式较大），则（多步）本地搜索可以在内部找到$ \ max \ mu（\ cdot）$ $ k^{o（k）} $的因子。作为我们结果的主要应用，我们显示了一个简单的几乎最佳的$ k^{o（k）} $ - 因子近似算法，用于非对称DPP的MAP推断。这是找到最大尺寸$ k $的第一个非平地乘法近似值，其中一个正方形（不必要的）矩阵$ l $，带有$ l+l+l^\ intercal \ intercal \ succeq 0 $。我们通过表明植根于离散凸分析的概念可以从局部随机步行的快速混合得出的交换不等式来建立采样和优化之间的联系。我们进一步将交换不平等与可合and核心集联系起来，以优化，将最新核心核心的最新结果推广到满足强烈雷利属性或具有log-conconcave生成多项式的任意分布。
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.