Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection

Abhimanyu Das, David KempeJMLR 2018 · OpenReview

TL;DR

This paper introduces the submodularity ratio, a mathematical tool to quantify how "close" a non-submodular function is to having the property of diminishing returns. By using this ratio, the authors provide the first strong multiplicative approximation guarantees for popular greedy heuristics like Forward Regression and Orthogonal Matching Pursuit (OMP), explaining why these algorithms perform so well in practice on problems like feature selection.

What Problem Does This Paper Address?

In the world of optimization, submodularity is a "gold standard" property. It formalizes the intuition of diminishing returns: adding an element to a small set helps more than adding it to a large set. When a function is submodular, a simple greedy algorithm is guaranteed to get you within at least 63% ($1-1/e$) of the optimal solution.

The problem? Many critical machine learning tasks—most notably subset selection for linear regression (picking the $k$ best features to predict a target)—are not submodular. Despite this, engineers and scientists have used greedy methods like Forward Regression for decades because they work remarkably well. Until this paper, there was a significant theoretical gap: we had "pessimistic" bounds based on data coherence that didn't explain the "optimistic" performance seen in real-world applications.

Methods

The authors bridge this gap by introducing the submodularity ratio ($\gamma$). If a function is perfectly submodular, $\gamma \ge 1$. If it's not, $\gamma$ measures the degree to which the "sum of individual gains" outweighs the "gain of the group."

The paper's contributions follow a logical progression:

  1. General Theory: They prove that for any monotone function with submodularity ratio $\gamma$, the greedy algorithm achieves a $(1 - e^{-\gamma})$ approximation.
  2. Spectral Connection: They show that for linear regression, the submodularity ratio is lower-bounded by the smallest $2k$-sparse eigenvalue of the data's covariance matrix. This connects discrete optimization directly to linear algebra.
  3. Algorithm Analysis: They apply this framework to provide new, tighter bounds for:
  4. Forward Regression: The standard greedy approach.
  5. Orthogonal Matching Pursuit (OMP): A common signal processing heuristic.
  6. Dictionary Selection: Selecting a set of basis vectors to represent multiple target signals.

Datasets

The authors validated their theoretical bounds using three datasets:

  • Boston Housing Data: A classic ML dataset with 15 features used to predict house prices.
  • World Bank Development Indicators: 29 socio-economic indicators used to predict life expectancy across 65 countries.
  • Synthetic Data: 29 features generated from a joint Gaussian distribution with controlled correlations to test the limits of the theory.

Key Insights and Ideas

  • The "Closeness" Principle: You don't need a function to be submodular to get good results; you just need it to be "approximately" submodular. This justifies the use of greedy heuristics on a much wider class of problems.
  • Beyond Coherence: Previous bounds relied on "coherence" (the maximum correlation between any two features). Coherence is a very "brittle" metric—one pair of highly correlated features can ruin the bound. The submodularity ratio is more robust because it looks at the eigenvalues of the feature space, capturing the global structure of the data.
  • The Alignment Effect: Empirical results showed that the submodularity ratio is often much higher than the smallest eigenvalues would suggest. This happens because the greedy algorithm only "cares" about the submodularity of the features it actually considers, and real-world target variables are often not aligned with the "noisy" or "singular" parts of the feature space.

Key Results

  • Theoretical Tightness: The authors improved the guarantees for Forward Regression from weak additive bounds to strong multiplicative ones (e.g., $1 - e^{-\lambda_{min}}$).
  • Greedy vs. Lasso: In their experiments, Forward Regression and OMP consistently performed near-optimally, often outperforming L1-regularization (Lasso) in terms of $R^2$ fit for a fixed sparsity level $k$.
  • Empirical $\gamma$: On the Boston Housing and World Bank data, the calculated submodularity ratio was significantly higher (often $>0.8$) than the raw spectral parameters, explaining why the greedy algorithm achieved nearly 90-95% of the optimal $R^2$.

Limitations and Future Work

  • Computational Complexity: Calculating the exact submodularity ratio $\gamma$ is NP-hard (just like finding the optimal subset itself). While the authors provide ways to estimate it using eigenvalues, getting a tight post-hoc guarantee for a specific dataset remains computationally expensive.
  • Monotonicity Constraint: The current framework focuses on monotone functions (where adding more features always improves the fit). Extending this to non-monotone functions—where adding features might increase noise or overfit—is a suggested direction for future research.
  • Fine-grained Parameters: The authors note a remaining gap between their theoretical $33\%$ guarantee (for $\gamma \approx 0.4$) and the observed $90\%+$ performance, suggesting that even more refined parameters are needed to fully capture the power of greedy search.

Summary updated

Abstract

We introduce the submodularity ratio as a measure of how “close” to submodular a set function $f$ is. We show that when $f$ has submodularity ratio $\gamma$, the greedy algorithm for maximizing $f$ provides a $(1-e^{-\gamma})$-approximation. Furthermore, when $\gamma$ is bounded away from 0, the greedy algorithm for minimum submodular cover also provides essentially an $O(\log n)$ approximation for a universe of $n$ elements. As a main application of this framework, we study the problem of selecting a subset of $k$ random variables from a large set, in order to obtain the best linear prediction of another variable of interest. We analyze the performance of widely used greedy heuristics; in particular, by showing that the submodularity ratio is lower-bounded by the smallest $2k$-sparse eigenvalue of the covariance matrix, we obtain the strongest known approximation guarantees for the Forward Regression and Orthogonal Matching Pursuit algorithms. As a second application, we analyze greedy algorithms for the dictionary selection problem, and significantly improve the previously known guarantees. Our theoretical analysis is complemented by experiments on real-world and synthetic data sets; in particular, we focus on an analysis of how tight various spectral parameters and the submodularity ratio are in terms of predicting the performance of the greedy algorithms.
BibTeX
@article{das2018approximate,
  author = {Abhimanyu Das and David Kempe},
  title = {{Approximate Submodularity and its Applications: Subset Selection, Sparse Approximation and Dictionary Selection}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=Yz-2cQD8NY},
}
Figure