Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
复制标题
通过非凸松弛和反集中的子行列式最大化
DOI：
10.1109/focs.2017.98
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
J. Ebrahimi;D. Straszak;Nisheeth K. Vishnoi
在最优化和计算机科学中出现的几个基本问题可以如下描述：给定向量v_1，.，v_m和[m]的子集的约束族B，在B中找到一个集合S，该集合S最大化由S中的向量所张成的单形的平方体积。一个令人鼓舞的例子是机器学习和信息检索中普遍存在的数据摘要问题，其中给出了一组表示文档或图像等数据的特征向量。向量集合的体积被用作其多样性的度量，并且对[m]施加分区或拟阵约束以确保资源或公平性约束。即使有一个简单的基数约束，这个问题也变成了NP-难的，并且从Khachiyan给出的一个r^{O（r）}近似算法开始受到了广泛的关注。最近，Nikolov和Singh提出了一个凸规划，并展示了当存在多个基数约束（即，当B对应于划分拟阵时）。他们对凸规划的完整性缺口的证明依赖于Gurvits的一个不等式，最近被推广到正则拟阵。这些估计算法是否可以转化为更有用的近似算法，也输出一个集合的问题仍然悬而未决。本文的主要贡献是给出了划分和正则拟阵的第一近似算法。我们提出了新的配方为这些拟阵的子行列式最大化问题，这减少了他们的问题，找到一个点，最大化的绝对值的非凸函数的概率单纯形的笛卡尔积。我们的结果的技术核心是一个新的反浓度不等式的依赖随机变量，产生这些功能，使我们能够将这些非凸函数的最优值，他们的值在一个随机点。不像以前的工作的约束次行列式最大化问题，我们的证明不依赖于真实的稳定性或凸性，并可能是独立的兴趣，在算法和复杂性，最近部署了反集中现象。
Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v_1,...,v_m in R^d and a constraint family B of subsets of [m], find a set S in B that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint, the problem becomes NP-hard and has received much attention starting with a result by Khachiyan who gave an r^{O(r)} approximation algorithm for this problem. Recently, Nikolov and Singh presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when B corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits, and was recently extended to regular matroids. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms – that also output a set – remained open.The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena has recently been deployed.