Subdeterminant maximization via nonconvex relaxations and anti-concentration

DOI10.1137/19M1309523zbMATH Open1506.68181arXiv1707.02757OpenAlexW3112877925MaRDI QIDQ3387758FDOQ3387758

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)

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.

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

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

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)

Cites Work

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

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)