This paper, presented at AAAI 2019, provides a rigorous theoretical bridge between the geometric world of vector spaces and the combinatorial world of submodular optimization. By leveraging Lattice Theory, the authors explain why simple greedy algorithms are so effective for complex tasks like Principal Component Analysis (PCA) and propose new, robust versions of these classic tools.
The Challenge of Subspace Selection
Many machine learning tasks involve subspace selection: finding a low-dimensional space that best represents your data. Standard examples include PCA and sparse dictionary selection. Mathematically, these are non-convex, continuous optimization problems, which are generally "hopeless" to solve optimally.
However, in practice, simple greedy algorithms often work remarkably well. Previous attempts to explain this used "set submodularity," treating vectors as a discrete collection of items. This approach fails because it ignores the underlying geometry—specifically, the fact that many different sets of vectors can span the exact same subspace. This paper seeks a "nicer" definition of submodularity that respects the structure of vector spaces.
Methodology: Lattices and DR-Submodularity
The authors move away from sets and toward Lattice Theory. They treat the collection of all possible subspaces as a "modular lattice," where the "meet" ($\wedge$) is the intersection of spaces and the "join" ($\vee$) is their sum.
The core contribution is the definition of two new properties:
- Downward DR-submodularity: A relaxation of traditional submodularity that captures the "diminishing returns" property in a way that fits the PCA objective function.
- Upward DR-submodularity: A complementary property that, when combined with the downward version, forms Directional DR-submodularity.
The authors then adapt three classic combinatorial algorithms to work on these lattices: a standard Greedy algorithm for monotone functions, a Greedy with Cost version for knapsack-style constraints, and a Double-Greedy algorithm for non-monotone functions like the "Quantum Max Cut."
Key Insights and Ideas
- PCA is Submodular (on a Lattice): The most significant "aha" moment is the proof that the standard PCA objective function is a monotone bidirectional DR-submodular function. This provides the missing theoretical link explaining why greedy eigenvector selection is optimal.
- Robustness via Concavity: By applying a concave function to the projection lengths (Generalized PCA), the authors show you can "diminish" the influence of very large outlier vectors, leading to more robust feature selection.
- Lattice Coherence: They introduce "mutual coherence of a lattice." They prove that if a lattice has low coherence, the greedy algorithm's approximation ratio for sparse dictionary selection improves. This suggests that the lattice formulation is more robust against highly correlated vectors than the standard set-based formulation.
- Quantum Generalization: They extend the concept of a "graph cut" to a "quantum cut" on subspaces, showing it remains directional DR-submodular even though it isn't monotone.
Key Results
The authors establish several provable approximation guarantees that match or extend the best-known bounds in discrete optimization:
- Approximation Guarantees: For modular lattices, the greedy algorithm achieves a $(1 - 1/e)$ approximation ratio for monotone functions under a dimension constraint.
- Generalized Bounds: For more complex "p-incremental" lattices, they establish a $(1 - e^{-1/p})$ bound.
- Non-monotone Maximization: The double-greedy algorithm provides a $1/3$ approximation ratio for unconstrained non-monotone directional DR-submodular functions.
Limitations and Future Work
While the framework is powerful, gaps remain. The approximation ratios for knapsack constraints and non-monotone problems on general lattices are currently weaker than those for simpler integer lattices. Furthermore, defining the lattice equivalent of "matroid constraints" remains an open challenge. The authors suggest that connecting this work to CAT(0) space theory could lead to even more powerful continuous optimization techniques in the future.
Summary updated