Subspace Selection via DR-Submodular Maximization on Lattices

So Nakashima, Takanori Maehara

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.

Figure 1: A modular lattice ($M_3$), representing the structure of vector subspaces where the join of different elements can result in the same subspace.

The core contribution is the definition of two new properties:

  1. Downward DR-submodularity: A relaxation of traditional submodularity that captures the "diminishing returns" property in a way that fits the PCA objective function.
  2. Upward DR-submodularity: A complementary property that, when combined with the downward version, forms Directional DR-submodularity.
Figure 2: A non-modular lattice ($N_5$) with a highlighted direction, illustrating the structural constraints and directional dependencies in the proposed optimization framework.

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

Abstract

The subspace selection problem seeks a subspace that maximizes an objective function under some constraint. This problem includes several important machine learning problems such as the principal component analysis and sparse dictionary selection problem. Often, these problems can be (exactly or approximately) solved using greedy algorithms. Here, we are interested in why these problems can be solved by greedy algorithms, and what classes of objective functions and constraints admit this property.In this study, we focus on the fact that the set of subspaces forms a lattice, then formulate the problems as optimization problems on lattices. Then, we introduce a new class of functions on lattices, directional DR-submodular functions, to characterize the approximability of problems. We prove that the principal component analysis, sparse dictionary selection problem, and these generalizations are monotone directional DRsubmodularity functions. We also prove the “quantum version” of the cut function is a non-monotone directional DR submodular function. Using these results, we propose new solvable feature selection problems (generalized principal component analysis and quantum maximum cut problem), and improve the approximation ratio of the sparse dictionary selection problem in certain instances.We show that, under several constraints, the directional DRsubmodular function maximization problem can be solved efficiently with provable approximation factors.
BibTeX
@inproceedings{nakashima2019subspace,
  author = {So Nakashima and Takanori Maehara},
  title = {{Subspace Selection via DR-Submodular Maximization on Lattices}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33014618},
}
Figure