000233898 001__ 233898
000233898 005__ 20190812210011.0
000233898 020__ $$a978-1-5386-3464-6
000233898 0247_ $$2doi$$a10.1109/Focs.2017.98
000233898 022__ $$a0272-5428
000233898 02470 $$2ISI$$a000417425300089
000233898 037__ $$aCONF
000233898 245__ $$aSubdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration
000233898 260__ $$bIeee$$c2017$$aNew York
000233898 269__ $$a2017
000233898 300__ $$a12
000233898 336__ $$aConference Papers
000233898 490__ $$aAnnual IEEE Symposium on Foundations of Computer Science
000233898 520__ $$aSeveral fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. 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 (B = (([m])(r))), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [1] who gave an r(O(r)) approximation algorithm for this problem. Recently, Nikolov and Singh [2] 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 [3], and was recently extended to regular matroids [4], [5]. 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.
000233898 6531_ $$aAnti-concentration
000233898 6531_ $$aSubdeterminant Maximization
000233898 6531_ $$aPolynomials
000233898 6531_ $$aNonconvexity
000233898 700__ $$aEbrahimi, Javad B.
000233898 700__ $$aStraszak, Damian
000233898 700__ $$0248256$$g243446$$aVishnoi, Nisheeth K.
000233898 7112_ $$dOCT 15-17, 2017$$cBerkeley, CA$$a58th IEEE Annual Symposium on Foundations of Computer Science (FOCS)
000233898 773__ $$t2017 Ieee 58Th Annual Symposium On Foundations Of Computer Science (Focs)$$q1020-1031
000233898 909C0 $$xU12921$$pTHL3$$0252575
000233898 909CO $$pconf$$pIC$$ooai:infoscience.tind.io:233898
000233898 937__ $$aEPFL-CONF-233898
000233898 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000233898 980__ $$aCONF