Subdeterminant maximization via nonconvex relaxations and anti-concentration

DOI10.1137/19M1309523MaRDI QIDQ3387758zbMATH OpenOpenAlexFDO

Authors J. B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi

Publication date 13 January 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.02757

zbMATH Keywords

approximation algorithmsmatroidsanti-concentrationsubdeterminant maximization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Abstract: Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors $v_1,ldots,v_{m}inmathbb{R}^d$ and a constraint family $calBsubseteq{2}^{[m]}$, find a set $SincalB$ 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 $calB$ 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.

Recommendations

• Maximizing determinants under partition constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Non-monotone submodular maximization under matroid and knapsack constraints
• Fast algorithms for maximizing submodular functions
• On largest volume simplices and sub-determinants

Cites work

• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• A generalization of permanent inequalities and applications in counting and optimization
• Algebraic algorithms for linear matroid parity problems
• Algebraic algorithms for matching and matroid problems
• Analysis of Boolean Functions
• Determinantal point processes for machine learning
• Determinantal probability measures
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
• Hyperbolic polynomials approach to van der Waerden/Schrijver-Valiant like conjectures, sharper bounds, simpler proofs and algorithmic applications
• Largest \(j\)-simplices in \(n\)-polytopes
• Linear matroid intersection is in quasi-NC
• Maximizing determinants under partition constraints
• On largest volume simplices and sub-determinants
• On selecting a maximum volume sub-matrix of a matrix and related problems
• On the complexity of approximating extremal determinants in matrices
• On the complexity of constrained determinantal point processes
• Random symmetric matrices are almost surely nonsingular.
• Randomized rounding for the largest simplex problem
• Real advantage
• Real stable polynomials and matroids: optimization and counting
• Singular spaces of matrices and their application in combinatorics
• The maximal-volume concept in approximation by low-rank matrices

Cited in

(2)

• Optimal sample complexity of subgradient descent for amplitude flow via non-Lipschitz matrix concentration
• Maximizing determinants under partition constraints

This page was built for publication: Subdeterminant maximization via nonconvex relaxations and anti-concentration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387758)