Title: Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration,
Abstract: Several fundamental problems that arise in optimization and computer science
can be cast as follows: Given vectors $v_1,\ldots,v_m \in \mathbb{R}^d$ and a
constraint family ${\cal B}\subseteq 2^{[m]}$, find a set $S \in \cal{B}$ that
maximizes the squared volume of the simplex spanned by the vectors in $S$. A
motivating example is the data-summarization problem in machine learning where
one is given a collection of vectors that represent data such as documents or
images. The volume of a set 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. 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 ${\cal B}$ corresponds to a partition matroid. This result was
recently extended to regular matroids in works of Straszak and Vishnoi, and
Anari and Oveis Gharan. 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 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.