On the complexity of constrained determinantal point processes
From MaRDI portal
Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Abstract: Determinantal Point Processes (DPPs) are probabilistic models that arise in quantum physics and random matrix theory and have recently found numerous applications in computer science. DPPs define distributions over subsets of a given ground set, they exhibit interesting properties such as negative correlation, and, unlike other models, have efficient algorithms for sampling. When applied to kernel methods in machine learning, DPPs favor subsets of the given data with more diverse features. However, many real-world applications require efficient algorithms to sample from DPPs with additional constraints on the subset, e.g., partition or matroid constraints that are important to ensure priors, resource or fairness constraints on the sampled subset. Whether one can efficiently sample from DPPs in such constrained settings is an important problem that was first raised in a survey of DPPs by cite{KuleszaTaskar12} and studied in some recent works in the machine learning literature. The main contribution of our paper is the first resolution of the complexity of sampling from DPPs with constraints. We give exact efficient algorithms for sampling from constrained DPPs when their description is in unary. Furthermore, we prove that when the constraints are specified in binary, this problem is #P-hard via a reduction from the problem of computing mixed discriminants implying that it may be unlikely that there is an FPRAS. Our results benefit from viewing the constrained sampling problem via the lens of polynomials. Consequently, we obtain a few algorithms of independent interest: 1) to count over the base polytope of regular matroids when there are additional (succinct) budget constraints and, 2) to evaluate and compute the mixed characteristic polynomials, that played a central role in the resolution of the Kadison-Singer problem, for certain special cases.
Recommendations
- Determinantal point processes for machine learning
- High-performance sampling of generic determinantal point processes
- Fixed-size determinantal point processes sampling for species phylogeny
- Asymptotic equivalence of fixed-size and varying-size determinantal point processes
- Maximizing determinants under partition constraints
Cites work
- A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
- A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Computing mixed discriminants, mixed volumes, and permanents
- Cooling Schedules for Optimal Annealing
- Counting Minimum Weight Spanning Trees
- Graphical models, exponential families, and variational inference
- Information, Physics, and Computation
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Mathematical Foundations of Computer Science 2005
- Mixed discriminants of positive semidefinite matrices
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Pipage rounding, pessimistic estimators and matrix concentration
- Random generation of combinatorial structures from a uniform distribution
- Real stable polynomials and matroids: optimization and counting
- Solving convex programs by random walks
Cited in
(15)- Discrete approximations of determinantal point processes on continuous spaces: tree representations and tail triviality
- Fixed-size determinantal point processes sampling for species phylogeny
- Spanning tree constrained determinantal point processes are hard to (approximately) evaluate
- Determinantal point processes for machine learning
- On sampling from multivariate distributions
- Subdeterminant maximization via nonconvex relaxations and anti-concentration
- High-performance sampling of generic determinantal point processes
- Ranking with Fairness Constraints
- Some Inapproximability Results of MAP Inference and Exponentiated Determinantal Point Processes
- Stability and complexity of mixed discriminants
- scientific article; zbMATH DE number 7164768 (Why is no real title available?)
- Maximizing determinants under partition constraints
- Extended L-ensembles: a new representation for determinantal point processes
- Computational complexity of normalizing constants for the product of determinantal point processes
- On sampling determinantal and Pfaffian point processes on a quantum computer
This page was built for publication: On the complexity of constrained determinantal point processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002639)
