Subspace Selection via DR-Submodular Maximization on Lattices

So Nakashima, Takanori Maehara

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 solved by 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. To answer this question, we formulate the problems as optimization problems on lattices. Then, we introduce a new class of functions, directional DR-submodular functions, to characterize the approximability of problems. We see that the principal component analysis, sparse dictionary selection problem, and these generalizations have directional DR-submodularities. We show that, under several constraints, the directional DR-submodular function maximization problem can be solved efficiently with provable approximation factors.

Introduction: The Geometry of Subspace Selection

Subspace selection is a fundamental challenge in machine learning, encompassing essential tasks like Principal Component Analysis (PCA) and sparse dictionary selection. While these problems are non-convex and theoretically difficult to solve exactly, simple greedy algorithms—which iteratively select the next best direction—often perform remarkably well in practice. This paper investigates the theoretical foundations of this success, moving beyond traditional set-based submodularity to a more robust framework based on lattice theory.

The Problem with Sets

Traditional approaches often treat subspace selection as picking a set of basis vectors. However, this approach is fundamentally flawed because different sets of vectors can span the exact same subspace. Set-based submodularity ignores the underlying geometric structure of vector spaces. By framing the problem on lattices—where the "join" ($\vee$) represents the direct sum and the "meet" ($\wedge$) represents the intersection—the authors can more accurately model the diminishing returns inherent in adding new dimensions to a subspace.

Lattice structure illustrating the join operation in subspace selection.

Methodology: Directional DR-Submodularity

Standard lattice submodularity is often too restrictive to capture the nuances of real-world machine learning objectives. To bridge this gap, the authors introduce directional DR-submodularity. This concept allows for an additive gap ($\delta$), relaxing the strict conditions of standard lattice submodularity while still providing a rigorous path to approximation guarantees.

The authors adapt three standard discrete optimization algorithms for this continuous lattice setting:

  1. Standard Greedy Algorithm: For height constraints (e.g., selecting a $k$-dimensional subspace).
  2. Modified Greedy Algorithm: For knapsack constraints, where different directions may have varying costs.
  3. Double-Greedy Algorithm: For unconstrained non-monotone problems (e.g., "Quantum Cut").
Greedy algorithms for height-constrained (left) and knapsack-constrained (right) maximization on lattices.

Key Insights and Results

The lattice-based framework provides several theoretical and practical breakthroughs:

  • PCA is Submodular: The authors prove that the objective function of standard PCA is a monotone bidirectional DR-submodular function. This provides a rigorous justification for why the greedy approach to PCA yields optimal results.
  • Robustness via Generalized PCA: By applying a concave function to the PCA objective, the authors create a "Generalized PCA" that is robust to outliers. In synthetic tests on a 3D dataset with a dominant cluster, this approach correctly identified the underlying 2D plane where standard PCA was "hijacked" by the majority class.
  • Approximation Guarantees: The paper establishes provable bounds for the adapted algorithms. The greedy algorithm for height constraints achieves a $(1 - e^{-1/p}, \text{gap})$ approximation. For knapsack constraints, the factor is $((1 - e^{-1})/2, \text{gap})$, and the double-greedy algorithm for non-monotone problems achieves a $1/3$ approximation.

Conclusion

By leveraging lattice theory and introducing directional DR-submodularity, this work provides a unified theoretical framework for understanding the efficacy of greedy algorithms in subspace selection. While computational bottlenecks remain—specifically the need to solve a non-convex optimization at each greedy step—this research opens new avenues for applying submodular optimization to continuous domains. Future work includes extending these results to matroid constraints and exploring more complex continuous relaxation algorithms on lattices.

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 solved by 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. To answer this question, we formulate the problems as optimization problems on lattices. Then, we introduce a new class of functions, directional DR-submodular functions, to characterize the approximability of problems. We see that the principal component analysis, sparse dictionary selection problem, and these generalizations have directional DR-submodularities. We show that, under several constraints, the directional DR-submodular 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