Source-linked AI summary
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
Abhimanyu Das, David Kempe
TL;DR
The paper asks how to select a sparse subset for linear prediction when standard guarantees do not explain greedy performance on correlated data. It analyzes greedy algorithms with submodularity and spectral tools, obtaining stronger guarantees for subset and dictionary selection. Experiments indicate that the submodularity ratio better predicts greedy performance than other spectral parameters, although the bounds do not fully predict observed near-optimal performance.
Problem
Subset selection seeks a small variable subset for predicting a target, but existing coherence- and spectral-based analyses do not explain strong greedy performance on correlated or near-singular data.
Method
The paper combines submodular-function analysis with spectral techniques, using the submodularity ratio to analyze greedy subset-selection and dictionary-selection algorithms.
Results
The paper obtains the strongest known theoretical guarantees for subset selection and dictionary selection, including factors 1 −e−γ for Forward Regression and 1 −e−(γ·λmin) for OMP.
Takeaways & Limitations
Experiments show that the submodularity ratio is a stronger predictor of greedy performance than previously used spectral parameters, including when covariance matrices are close to singular.
Takeaways & Limitations
The bounds do not fully predict the observed near-optimal performance of Forward Regression and OMP, motivating finer-grained parameters and further study of when R2 submodularity matters.
Abstract
from arXiv · showhide
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. This problem can be viewed in the context of both feature selection and sparse approximation. We analyze the performance of widely used greedy heuristics, using insights from the maximization of submodular functions and spectral analysis. We introduce the submodularity ratio as a key quantity to help understand why greedy algorithms perform well even when the variables are highly correlated. Using our techniques, we obtain the strongest known approximation guarantees for this problem, both in terms of the submodularity ratio and the smallest k-sparse eigenvalue of the covariance matrix. We further demonstrate the wide applicability of our techniques by analyzing 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; the experiments show that the submodularity ratio is a stronger predictor of the performance of greedy algorithms than other spectral parameters.
1 Introduction
The paper studies subset selection for linear prediction and sparse approximation, focusing on why greedy algorithms can work despite correlated variables. It introduces submodularity-ratio and spectral analyses, derives guarantees for subset and dictionary selection, and evaluates their predictive value experimentally.
- Problem formulation: Subset selection chooses k variables from n candidates to maximize the R2 fit of a linear prediction, with applications in feature selection and sparse approximation.The formulation uses normalized covariances between observation variables and a target variable.
- Problem formulation: The problem is NP-hard, while convex relaxation methods require regularization tuning and do not directly control the target sparsity level k.Greedy methods instead iteratively add or remove variables according to fit-related measures.
- Motivation: Previous coherence- and spectral-condition bounds often fail to explain strong greedy performance on highly correlated or near-singular data.Extending sparse-recovery results to subset selection yields weak additive bounds and introduces dependence on the largest k-sparse eigenvalue.
- Main contributions: The submodularity ratio measures how closely the R2 objective approximates submodularity and can explain constant-factor performance when it is bounded away from 0.Its analysis complements spectral bounds because the ratio is lower-bounded by the smallest k-sparse eigenvalue and can be significantly larger.
- Main contributions: The framework also strengthens greedy dictionary-selection guarantees and experiments find the submodularity ratio more predictive than other spectral parameters.Experiments compare greedy and L1-relaxation algorithms on real-world and synthetic datasets.
- Main contributions: Forward Regression and OMP achieve approximation factors 1 −e−γ and 1 −e−(γ·λmin), respectively, relative to the optimum.Here γ and λ are the relevant submodularity and sparse-eigenvalue parameters.
2 Preliminaries
Subset selection chooses a small variable set and linear predictor to maximize R2, with dictionary selection extending the setup to multiple predictors. The paper defines approximate submodularity through the submodularity ratio and relates it to sparse eigenvalues, while noting computational and nonsingularity constraints.
- Subset Selection: The covariance matrix C and covariance vector b encode pairwise observation-variable covariances and covariances between observations and the predictor.For a selected set S, the optimal regression coefficients are aS = C_S^-1 b_S, and the objective is expressed using C and b.
- Subset Selection: Subset selection chooses at most k variables and a linear predictor maximizing the squared multiple correlation R2.R2 measures the fraction of Z's variance explained by the selected variables.
- Dictionary Selection: Dictionary selection generalizes subset selection to multiple predictor variables and maximizes their average R2 fit using a shared dictionary.It selects at most d observation variables, with at most k dictionary vectors used for each predictor.
- Technical Conditions: The analysis assumes CS is nonsingular, although some results can extend to singular matrices using the Moore–Penrose generalized inverse; computing λmin(C, k) is NP-hard.Efficient approximations are described for some scenarios.
- Submodularity Ratio: The submodularity ratio measures how much more a set function can gain from adding a subset than from adding its elements individually.For the R2 objective, the ratio is specialized using residualized covariances after conditioning on the current set.
- Submodularity Ratio: γU,k is bounded below by λmin(C, k + |U|), and therefore by the smallest eigenvalue of C; with |U| = k, γU,k ≥ λmin(C, 2k).The smallest 2k-sparse eigenvalue can nevertheless be a weak lower bound.
3 Algorithms Analysis
This section analyzes Forward Regression, Orthogonal Matching Pursuit, and Oblivious greedy algorithms for subset selection, deriving approximation guarantees under submodularity and spectral conditions.
- Algorithms analyzed: The analysis covers Forward Regression, Orthogonal Matching Pursuit, and the Oblivious algorithm for subset selection.The optimum is the largest R2 value achievable by any set of k variables.
- Forward Regression: Forward Regression selects variables iteratively to maximize the resulting R2 fit.It is described as a standard algorithm used in medical, social, and economic domains.
- Forward Regression: Forward Regression receives approximation guarantees expressed through the submodularity ratio and covariance-matrix eigenvalue parameters.The section states that its theorem provides multiple guarantees, including one obtained through repeated inductive bounds.
- Orthogonal Matching Pursuit: Orthogonal Matching Pursuit chooses the variable with maximum residual covariance magnitude at each iteration.The residual is formed after conditioning on the variables already selected.
- Orthogonal Matching Pursuit: The OMP analysis combines residual-variance bounds with eigenvalue arguments to derive multiplicative approximation guarantees.A lemma lower-bounds the residual variance using the smallest eigenvalue of the joint covariance matrix.
- Oblivious: The Oblivious baseline selects the k variables with the largest individual covariance values with the target.Its guarantees are stated in terms of λmax(C, k) and the optimal R2 value.
4 Dictionary Selection Bounds
This section extends approximate-submodularity analysis to dictionary selection, obtaining tighter multiplicative guarantees for SDSMA and SDSOMP than earlier bounds.
- Problem and framework: The dictionary-selection objective chooses at most d feature vectors whose best k-element subsets provide high average R2 fit across s target vectors.The framework is presented as a wider application of approximate submodularity.
- SDSMA: SDSMA iteratively selects dictionary elements using a modular approximation to the per-target R2 objective.The inner maximization over k-element subsets can be computed using the Oblivious algorithm.
- SDSMA: The SDSMA analysis provides a multiplicative approximation guarantee relative to the optimal dictionary.The proof uses the monotonicity and submodularity of the modular surrogate objective.
- SDSMA: The new SDSMA bounds significantly improve the previous additive guarantee, which becomes trivial when μ(C) > Θ(1/k).The cited comparison identifies the failure threshold as occurring when even one variable pair has moderate correlation.
- SDSOMP: SDSOMP also receives a multiplicative approximation guarantee, but its guarantee is weaker than SDSMA’s.The paper states that the new SDSOMP bounds are stronger than prior additive bounds while remaining weaker than SDSMA’s bounds.
- SDSOMP: SDSOMP generalizes Orthogonal Matching Pursuit to dictionary selection by using OMP to approximate each candidate’s contribution.At each iteration it evaluates candidate additions through the OMP-selected subsets for the target vectors.
5 Experiments
Experiments compare greedy and L1-relaxation methods across real-world and synthetic data, alongside submodular and spectral parameters. Forward Regression is optimal or near-optimal, while the submodularity ratio better predicts greedy performance than eigenvalue- or condition-number-based measures.
- Algorithm performance: Forward Regression performs optimally or near-optimally on all data sets, OMP is slightly worse, Lasso performs worse, and Oblivious performs worst.The observed performance ordering matches the ordering of the theoretical guarantees for the greedy algorithms.
- Algorithm performance: On the World Bank data, all algorithms perform well with only 2–3 features because adolescent birth rate is highly predictive of life expectancy.The first feature selected by every algorithm already contributes high R2 value.
- Parameter behavior: The real-world covariance matrices are nearly singular, with small λmin(C) values and highly correlated variable pairs already evident from small λmin(C, 2).Bounds based on λmin(C, k), λmin(C, 2k), or κ(C, k)^−1 are therefore weak, with the inverse condition-number bound weakest among them.
- Parameter behavior: Submodularity ratios are almost 5 times larger on average than corresponding λmin(C) values and exceed 0.2, making them better practical predictors of greedy performance.The ratios are not monotonically decreasing in k because γSFR,k depends on the selected set SFR, which changes with k.
- Parameter behavior: On synthetic data, λmin(C) ≈0.11 while the submodularity ratio is close to 1 for every k, and the R2 curve is concave.The results indicate submodularity-based bounds capture the observed behavior better than simple eigenvalue-based bounds.
- Theory versus practice: The theoretical bounds still do not fully predict Forward Regression and OMP’s near-optimal real-world performance.For Forward Regression, γSFR,k below 0.4 implies a guarantee of roughly 1 − e^−0.4 ≈33%, despite near-optimal observed performance.
- Theory versus practice: Pruning sets with ǫ = 0.2 raises Forward Regression’s estimated γSFR,k to more than 0.8, reducing the gap between theoretical bounds and experiments.The paper identifies characterizing which sets exhibit relevant submodular behavior as a direction for future work.
6 Discussion and Concluding Remarks
The paper analyzes greedy algorithms through submodularity ratio and spectral techniques, establishing strong approximation guarantees for subset and dictionary selection.
- Submodularity ratio captures how closely the R2 statistical-fit objective approximates submodularity.
- The combined submodular and spectral analysis yields the strongest known approximation guarantees for subset selection and dictionary selection.
- The bounds help explain why greedy algorithms perform well even when variables are strongly correlated.