Source-linked AI summary
On the Complexity of Constrained Determinantal Point Processes
L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, Nisheeth K. Vishnoi
TL;DR
The paper asks whether DPPs can be sampled efficiently under combinatorial constraints such as fairness, partition, or budget requirements. Using generating polynomials and the equivalence between counting and sampling, it establishes efficient exact algorithms for unary-described constraints and hardness for binary-described ones. The framework also yields results for regular matroids and mixed characteristic polynomials.
Problem
Efficient sampling from DPPs with additional combinatorial constraints was an open problem important for fairness, resource, and prior constraints.
Source: §1 · pp. 2–3Method
The paper views constrained probabilities as coefficients of generating polynomials and reduces sampling to counting through polynomial evaluation and interpolation.
Source: §1.1 · p. 4Results
Unary-described constraints admit exact efficient sampling, whereas binary-described constraints make counting #P-hard and determinantal equality counting at least as hard to approximate as mixed discriminants.
Source: §1 · p. 3, §1.1 · p. 5Takeaways & Limitations
The framework supports efficient sampling for practical constraint classes and extends to budgeted regular-matroid counting and special cases of mixed characteristic polynomials.
Source: §1.1 · p. 6The counting-oracle argument does not directly generalize to approximate counting because it relies on interpolation.
Source: §8.2 · p. 18
Abstract
from arXiv · showhide
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.
1 Introduction
The paper resolves the complexity of sampling from constrained DPPs by using generating polynomials, obtaining efficient exact algorithms for unary-described constraints and hardness for binary-described constraints.
1 Introduction
- DPPs assign higher probability to diverse subsets through determinants and support efficient sampling, motivating their use in summarization, recommendation, and related applications.A subset’s determinant measures the squared volume spanned by its feature vectors.Source: §1 · p. 2
- Constrained DPPs incorporate fairness, budget, and other combinatorial requirements, but their complexity had remained open because rejection sampling and common partition heuristics can fail.The constrained family may have arbitrarily small probability mass, while independent sampling across parts misses the required negative correlations.Source: §1 · pp. 2–3
- The paper gives the first resolution: exact polynomial-time sampling for unary-described constraints, including fairness, partition, and budget cases, versus #P-hardness for binary-described constraints.The unary algorithms run polynomially in the ground-set size and the magnitude of the cost description.Source: §1 · p. 3
1.1 Our Framework and Results
- The partition-DPP connection also enables polynomial-time computation of top mixed-characteristic-polynomial coefficients and exact evaluation for constant-dimensional matrix subspaces.These polynomials played a central role in the proof of the Kadison–Singer conjecture.Source: §1 · p. 3, §1.1 · p. 6
- Budget-constrained counting is polynomial-time in m and ∥c∥1, extending to equality, value-set, and constantly many simultaneous constraints.For DPP weights, this yields sampling with probability proportional to det(L_S,S), including linear families and constantly many partition parts.Source: §1.1 · pp. 4–5
- The framework reduces constrained counting to coefficients of univariate polynomials and uses efficiently evaluable DPP generating polynomials, with sampling obtained through counting.The counting–sampling equivalence applies without assumptions on how the constraint family is accessed.Source: §1.1 · pp. 4–5
- The same polynomial method solves budgeted counting and sampling over bases of regular matroids, extending applications beyond constrained DPPs.The result uses the efficiently computable generating polynomial of the regular-matroid basis indicator measure.Source: §1.1 · p. 5
- When costs and budgets are binary encoded and potentially exponential, BCount is #P-hard and determinantal ECount is at least as hard to approximate as mixed discriminants.The reduction uses partition-constrained DPPs with a large, super-constant number of parts; related hardness also reaches perfect matchings in general graphs.Source: §1.1 · pp. 5–6
2 Counting with Budget Constraints
The section reduces budget-constrained counting to coefficient extraction from a univariate polynomial, using interpolation to recover the needed coefficients.
2 Counting with Budget Constraints
- Substituting z^{c_i} for each variable turns the generating polynomial into h(z), whose coefficient of z^d sums weights of sets with cost d.Summing coefficients through degree C gives the budget-at-most-C count; negative costs are handled with a modified polynomial.Source: §2 · pp. 6–7
- Because h has degree at most ∥c∥1 for nonnegative costs, evaluating it at ∥c∥1 + 1 inputs and interpolating recovers its coefficients.The resulting runtime is polynomial in the unary magnitude of the cost vector, together with the evaluation-oracle runtime.Source: §2 · p. 6
- The resulting algorithm computes the budget-constrained sum using oracle access to the generating polynomial.This is stated as an efficient solution to BCount when costs are not too large in magnitude.Source: §2 · p. 7
3 Determinantal Point Processes
For determinantal measures, the generating polynomial is efficiently evaluable through a determinant identity, enabling exact counting and sampling under structured constraints.
3 Determinantal Point Processes
- For a determinantal function, det(V^⊤XV + I) equals the generating polynomial whose coefficient of x_S is det(L_S,S).This gives efficient evaluation at arbitrary variable assignments via determinant computation.Source: §3 · p. 7
- Exact counting yields exact sampling for budget-constrained DPPs, and the same approach extends to linear families.The sampling reductions use the equivalence between counting and sampling.Source: §3 · pp. 7–8
- Introducing one variable per linear constraint makes each coefficient encode the total determinantal weight of sets attaining a specified vector of costs.Interpolation over these variables recovers the coefficients needed to sum over the allowed cost sets.Source: §3 · p. 8
- Partition families with a constant number of parts admit polynomial-time DPP sampling because their cardinality constraints have a succinct linear-family representation.Each part is represented by an indicator cost vector and a singleton allowed-cost set.Source: §3 · pp. 8–9
4 Hardness Result
The hardness section establishes a binary-encoding boundary: unary costs permit polynomial-time counting, whereas binary costs lead to #P-hardness through mixed discriminants.
4 Hardness Result
- When costs are binary encoded, BCount is #P-hard, and efficient approximation for the exact-cost variant would imply schemes for difficult counting problems.The stated implications include perfect matchings in non-bipartite graphs and mixed discriminants.Source: §4 · p. 9
4.1 Mixed Discriminants
- Mixed discriminants are #P-hard and lack a known FPRAS, while the best cited polynomial-time approximations have exponentially large approximation ratios.They can encode the permanent, but the passage distinguishes their approximation status from the permanent’s.Source: §4.1 · p. 9
- Given PSD n × n matrices, a polynomial-time reduction outputs a PSD matrix L and integer cost data, using rank-one decompositions indexed by m=n^2 pairs, with ||c||1 ≤ 2^O(n log n).Source: §4.1 · pp. 9–10
- The reduction makes exact-cost determinantal counting at least as hard as computing mixed discriminants; solving BCount at C and C−1 recovers the exact-cost sum.Thus the at-most-budget formulation inherits the mixed-discriminant hardness.Source: §4.1 · p. 10
5 Mixed Discriminants and Mixed Characteristic Polynomials
This section develops reductions between mixed discriminants, mixed characteristic polynomials, and partition-constrained DPP counting, yielding polynomial-time algorithms for selected coefficients and special matrix families.
5 Mixed Discriminants and Mixed Characteristic Polynomials
- The section situates these algorithms in the study of mixed characteristic polynomials, which played a crucial role in the proof of the Kadison-Singer conjecture.The paper uses mixed discriminant identities to make selected coefficient computations algorithmic.Source: §5 · pp. 11–12
- Higher-degree coefficients reduce to counting for partition-constrained DPPs with constantly many parts, establishing an algorithmic bridge between the two problems.The reduction is used as a subroutine for computing coefficients of mixed characteristic polynomials.Source: §5 · p. 11
- The coefficient of x^(d−k) in a mixed characteristic polynomial is computable in poly(m^k) time for symmetric PSD matrices.The method reduces coefficient computation to mixed discriminants with repeated identity matrices and then to partition-constrained DPP counting.Source: §5 · pp. 11–12
- Approximating mixed discriminants and coefficients of mixed characteristic polynomials are computationally equivalent through an approximation-preserving reduction.A coefficient sum of exponentially many mixed discriminants is represented by one mixed discriminant of larger matrices.Source: §5 · p. 13
- When the input matrices span a k-dimensional linear space, the entire mixed characteristic polynomial is computable deterministically in poly(m^k) time.The result follows by combining the reduction with an algorithm for mixed discriminants on bounded-dimensional matrix spaces.Source: §5 · p. 14
6 Budget-Constrained Sampling and Counting for Regular Matroids
The paper extends budgeted counting and sampling from spanning trees to bases of regular matroids, using efficiently computable generating polynomials from totally unimodular representations.
6 Budget-Constrained Sampling and Counting for Regular Matroids
- The result covers uniformly random spanning trees subject to a cost budget and generalizes budgeted spanning-tree sampling to regular matroids.Spanning trees are bases of the graphic matroid, a regular matroid.Source: §6 · p. 14
- Counting and sampling regular-matroid bases of cost at most C are solvable in time polynomial in m and ||c||_1.The algorithms output the number of feasible bases and a random feasible basis, respectively.Source: §6 · p. 14
- The proof represents regular matroids with totally unimodular matrices and uses their basis generating polynomial as an efficiently computable polynomial.This makes the budgeted counting theorem applicable, after which counting–sampling equivalence gives efficient sampling.Source: §6 · pp. 14–15
7 Hardness for Spanning Trees
This section reduces counting perfect matchings to counting spanning trees with a specified total cost, establishing hardness for budget-constrained spanning-tree counting.
7 Hardness for Spanning Trees
- BCount is at least as hard as counting perfect matchings in a non-bipartite graph.The reduction maps perfect matchings to budget-constrained spanning trees.Source: §7 · p. 15
- The reduction adds zero-cost complete-graph edges and assigns original edges base-b costs encoding vertex degrees without carryovers.For an original edge ij, the cost is c_e = b^i + b^j, with b chosen larger than the number of edges.Source: §7 · p. 16
- A spanning tree with target cost C has original-edge intersection forming a perfect matching, because the base-b digits force every vertex degree to equal one.Edges outside the original graph contribute zero cost.Source: §7 · p. 16
- Each perfect matching corresponds to exactly α = n^2/2 (2n)^(−n/2) spanning trees of target cost C.After contracting the matching, the added edges form a complete multigraph with four parallel edges between every pair, whose spanning-tree count is obtained via Cayley’s formula.Source: §7 · p. 16
8 Equivalence Between Counting and Sampling
The section proves that approximate counting and approximate sampling are polynomially equivalent for nonnegative measures with generating-polynomial oracle access, in both directions.
8 Equivalence Between Counting and Sampling
- Approximate C-counting and approximate C-sampling differ in time complexity by at most a poly(m, ε^−1) multiplicative factor.The equivalence applies to arbitrary subset families C when the generating polynomial can be queried.Source: §8 · pp. 16–17
8.1 Counting Implies Sampling
- Exact counting implies exact sampling through sequential conditioning on element inclusion decisions, using polynomially many counting and generating-polynomial queries.At each step, the sampler computes a conditional inclusion probability and flips a biased coin.Source: §8.1 · pp. 17–18
- The conditional probabilities needed for sampling are computed by modifying the generating polynomial and extracting a coefficient through interpolation.The relevant polynomial has degree at most |Y|, so |Y|+1 evaluations suffice for exact interpolation.Source: §8.1 · p. 18
8.2 Sampling Implies Counting
- Sampling implies approximate counting by repeatedly sampling under restrictions S ⊆ U and estimating element-removal probabilities.The resulting counting oracle uses poly(m, 1/ε) samples and has exponentially small failure probability in m.Source: §8.2 · pp. 18–19
- The interpolation argument does not directly extend to approximate counting oracles, although evaluating at a sufficiently large input provides an alternative for the top coefficient.This is the stated limitation of the direct proof technique.Source: §8.2 · p. 18
- The reverse implication relies on recursively shrinking U until the probability of selecting all of U is sufficiently high, then multiplying estimated conditional probabilities.The analysis uses Lemmas 8.6 and 8.7 to find an element with sufficiently large exclusion probability.Source: §8.2 · pp. 19–20