Hardness of Maximum Likelihood Learning of DPPs

This paper proves Kulesza's conjecture by demonstrating that computing the maximum likelihood of a Determinantal Point Process (DPP) is NP-complete, even for approximations within a factor of $1-O(\frac{1}{\log^9{N}})$, via a reduction from a gap instance of the 3-Coloring problem on hypergraphs.

The Gist

The Big Picture: The "Diversity" Problem

Imagine you are a curator for a museum. You have a massive collection of art (your data), and you want to create a small, perfect exhibit (a subset) that shows the best variety of styles without repeating the same thing twice.

In the world of Machine Learning, this is called a Determinantal Point Process (DPP). It's a mathematical tool designed to pick diverse, representative groups of items.

• The Goal: If you have a pile of photos, a DPP helps you pick 10 photos that show a dog, a cat, a bird, a car, a tree, etc., rather than 10 photos of just dogs.
• The Catch: To make the DPP work, you need to tune its "knobs" (parameters). You want to find the specific settings that make the DPP most likely to have picked the exact data you have. This is called Maximum Likelihood Learning.

The Mystery: Is it Easy or Hard?

For over a decade, computer scientists have been trying to figure out: Can we write a fast computer program to find the perfect settings for these knobs?

• The Optimists: Some thought, "Sure, it's just math. We can solve it."
• The Skeptics (Kulesza): A researcher named Kulesza guessed in 2011 that it's actually impossible to solve efficiently. He suspected it was "NP-hard," which is a fancy way of saying, "If you try to solve this perfectly, you might as well be trying to count every grain of sand on Earth; it will take longer than the universe has existed."

However, no one could prove it. It was just a hunch.

The Breakthrough: Proving the Skeptic Right

This paper is the "smoking gun." The authors (Grigorescu, Juba, Wimmer, and Xie) finally proved Kulesza was right.

The Main Result:
They proved that finding the perfect settings for a DPP is not just hard; it's provably impossible to do quickly for large datasets. In fact, even finding a "good enough" answer (an approximation) is incredibly difficult.

The Analogy: The Master Chef vs. The Food Critic
Imagine you are a Master Chef (the DPP) trying to recreate a specific dish based on a Food Critic's notes (the data).

• The Problem: The critic's notes are vague. There are millions of ways to combine ingredients.
• The Paper's Finding: The authors proved that there is no shortcut recipe. To find the exact combination that matches the critic's notes perfectly, you have to taste-test every single possible combination of ingredients. Even if you just want a dish that tastes "pretty close," the math says you still have to taste almost everything.

How Did They Prove It? (The Magic Trick)

To prove something is impossible, you usually show that if you could solve it, you could also solve a problem everyone already knows is impossible.

1. The Starting Point: They started with a classic, unsolvable puzzle called 3-Coloring. Imagine you have a map of countries, and you need to color them Red, Green, or Blue so that no two touching countries have the same color. If the map is messy, figuring this out is a nightmare.
2. The Transformation: They turned this map puzzle into a DPP learning problem. They showed that if you could find the perfect DPP settings for their specific data, you could instantly solve the map coloring puzzle.
3. The Connection (Vector Coloring): Here is the clever part. They realized that a DPP works by turning items into vectors (arrows in space).
   • If two items are similar, their arrows point in the same direction.
   • If they are different (diverse), their arrows point in opposite directions (orthogonal).
   • To maximize diversity, the DPP wants the arrows for a group of items to form a perfect 90-degree angle (like the X, Y, and Z axes).
   • The authors showed that solving the DPP is mathematically identical to trying to arrange these arrows so they are all perfectly 90 degrees apart. If the map (the data) is "messy" (not 3-colorable), you can't arrange the arrows perfectly.

The Conclusion: Because the map coloring problem is hard, the DPP learning problem is also hard.

The Silver Lining: A "Good Enough" Solution

If the perfect solution is impossible, is there any hope?

Yes! The authors didn't just say "It's impossible." They also built a simple, fast algorithm that gives a "good enough" answer.

The "Diagonal" Trick:
Instead of trying to figure out complex relationships between every item, their algorithm just looks at how often each item appears in the data.

• The Metaphor: Imagine you are picking a playlist. Instead of analyzing the musical theory of every song to ensure diversity, you just pick the songs that appear most often in your "Top 100" list. It's not the perfect playlist, but it's a very good one, and you can do it instantly.

They proved this simple method works surprisingly well, especially when no single item dominates the data (e.g., you don't have 90% of your photos being pictures of cats).

Why Does This Matter?

1. For Researchers: It stops people from wasting time trying to find a "perfect" algorithm for DPPs. We now know we have to settle for approximations.
2. For Practitioners: It tells us that the "heuristic" methods (guess-and-check methods) currently used in industry are actually the best we can do. We shouldn't expect a magic bullet to appear tomorrow.
3. For the Future: It opens the door to new questions. If we can't solve it perfectly, what are the best ways to approximate it? And under what specific conditions (like when data is generated by a real DPP) might it become easier?

Summary in One Sentence

The authors proved that finding the perfect mathematical settings to make a computer pick diverse data is as hard as solving an unsolvable puzzle, but they also showed that a simple, fast "rule of thumb" can get you a very good result most of the time.

Technical Summary

1. Problem Statement

The paper addresses the computational complexity of Maximum Likelihood Estimation (MLE) for Determinantal Point Processes (DPPs).

• Context: DPPs are probabilistic models used to select diverse, representative subsets of data (negative correlation). They are defined by a marginal kernel matrix $K$ (positive semidefinite with eigenvalues in $[0, 1]$).
• The Task: Given a training dataset consisting of $m$ subsets of a ground set of size $N$, the goal is to find a kernel $K$ that maximizes the likelihood of observing these subsets.
• The Gap: While DPPs are widely used, existing learning algorithms either restrict the search to specific parametric families or use local heuristics (like Expectation-Maximization) without theoretical guarantees of optimality.
• The Conjecture: Kulesza (2011) conjectured that finding the maximum likelihood DPP is NP-hard, but a formal proof was missing. Conversely, some recent work suggested a polynomial-time algorithm might exist.

2. Methodology and Approach

The authors resolve the conjecture by proving that approximating the maximum log-likelihood is NP-hard. Their approach involves a sophisticated chain of reductions from graph coloring problems to the DPP learning problem.

A. Reduction Chain

The proof follows the sequence illustrated in Figure 1 of the paper:

1. Max-3SAT to 3-Coloring: They start with the hardness of approximating Max-3SAT (specifically bounded-occurrence instances). They reduce this to the 3-Coloring problem on bounded-degree graphs using the construction by Bogdanov, Obata, and Trevisan (BOT graphs).
2. Enhancing BOT Graphs: To ensure robustness against edge deletions (crucial for the "gap" in the reduction), they enhance the BOT graph construction using strong expanders (Alon and Capalbo). This ensures that if a graph is far from 3-colorable, it remains far from 3-colorable even after removing a small fraction of edges.
3. 3-Coloring to DPP Learning: They transform the 3-Coloring instance into a DPP learning instance.
   • They construct a 3-uniform hypergraph where vertices represent graph nodes and edges represent hyperedges (triplets).
   • The training data for the DPP consists of these hyperedges.
   • Key Insight: A DPP kernel $K$ can be factored as $K = Q^\top Q$. The columns of $Q$ represent vectors in $\mathbb{R}^k$. For a subset of size 3 to have high probability (high likelihood), the corresponding vectors must be nearly orthogonal.
   • Thus, maximizing the DPP likelihood is equivalent to finding a "vector coloring" where adjacent vertices in the hypergraph have orthogonal vectors.

B. Technical Challenges & Solutions

• Rank Reduction: The optimal kernel might have high rank. The authors prove (Theorem 7) that if a kernel has near-optimal likelihood, there exists a rank-3 kernel with nearly the same likelihood. This allows them to restrict the analysis to 3-dimensional vector colorings.
• Decoding Vector Coloring to Discrete Coloring: They show that if a vector coloring is "almost perfect" (vectors are nearly orthogonal), one can decode a valid discrete 3-coloring by removing a small fraction of "noisy" edges. This relies on the robustness of the expander graphs used in the construction.
• Diagonal Constraints: They prove that for the optimal kernel, the diagonal entries must match the empirical frequencies of the elements in the training data (Theorem 5). This decouples the "importance" (norm) of vectors from their "diversity" (direction).

3. Key Contributions and Results

A. Hardness of Approximation (Main Result)

The authors prove Kulesza's conjecture and establish a stronger hardness result:

• Theorem 1: It is NP-hard to compute a $(1 - O(1/\log^9 N))$-approximation of the maximum log-likelihood for a DPP on a ground set of size $N$.
• This implies that even finding a solution close to the optimal likelihood is computationally intractable. The difficulty is inherent to the problem itself, not just a specific representation of the kernel.

B. Approximation Algorithm

Despite the hardness, the authors provide a simple polynomial-time algorithm that achieves a non-trivial approximation:

• Algorithm: Construct a diagonal kernel $K$ where $K_{ii}$ is the empirical frequency of element $i$ in the dataset (i.e., the probability that element $i$ appears in a random subset).
• Performance:
  • General Case: Achieves a $\frac{1}{(1+o(1))\log m}$-approximation (where $m$ is the number of subsets).
  • Sparse Case: If every element appears in at most $O(1/N)$ of the subsets (a common scenario in practice), the approximation factor improves to $1 - \frac{1+o(1)}{\log N}$.
• Significance: This algorithm serves as a benchmark. While heuristics might perform better in practice, this provides the first theoretical worst-case guarantee.

4. Significance and Implications

1. Resolution of Open Problems: The paper definitively settles the complexity of DPP learning, confirming that the problem is NP-hard and that no polynomial-time algorithm can guarantee an optimal solution (unless P=NP).
2. Theoretical Limits: It establishes that the "gap" between the optimal likelihood and any efficiently computable likelihood is significant. This explains why heuristic methods (EM, MCMC) are necessary in practice and why they often get stuck in local optima.
3. Connection to Geometry and Coloring: The work deepens the understanding of the relationship between DPPs, vector coloring, and graph expansion. It demonstrates that learning a DPP is essentially a continuous relaxation of a discrete graph coloring problem.
4. Practical Benchmark: The proposed diagonal kernel algorithm offers a baseline for practitioners. If a heuristic performs significantly better than this diagonal kernel, it suggests the heuristic is capturing structural dependencies; if it performs similarly, the data may be well-approximated by independent probabilities.
5. Future Directions: The paper opens questions about learning DPPs under "realizability" assumptions (where data is actually generated by a DPP) versus the "agnostic" setting (worst-case data). It suggests that average-case hardness might be the appropriate framework for analyzing practical learning scenarios.

Summary

In essence, the paper proves that learning the optimal parameters for a Determinantal Point Process is computationally intractable (NP-hard to approximate). It achieves this by reducing the problem to 3-Coloring on robust expander graphs, showing that high likelihood implies a near-perfect vector coloring which can be decoded into a graph coloring. While finding the optimum is hard, a simple diagonal kernel provides a provable, albeit weak, approximation, setting a theoretical floor for what can be achieved efficiently.