Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection

By Abhimanyu Das, David Kempe. 2011

517 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “…with The proof of Proposition 3.1 follows by writing F as the sum of n (cid:96) +1 sparse linear regression problems , and from the relation established in [Elenberg et al., 2016, Das and Kempe, 2011] between weak submodularity and sparse eigenvalues of the covariance matrix (see Appendix B.1).”
Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, background): “Obtaining a minimal set of observations to project on is even more diﬃcult and only the recent work of Das and Kempe (2011) provides usable performance guarantees for it.”
Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, background): “As a consequence, at least for the linear regression case, such greedy algorithms produce provably good solutions, if we restrict the weights to be binary [15, 26].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “Note however that the condition on suppressors is rather strong, although it can be appropriately relaxed in order to obtain more widely applicable guarantees for subset selection [57].”
GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning (2020, methodology): “While this definition is different from the notion of approximate submodularity (Das and Kempe 2011).”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “For example, γ -weakly submodular optimization techniques have been used in feature selection [Das and Kempe, 2011, Khanna et al., 2017], anytime linear prediction [Hu et al., 2016], interpretation of deep neural networks [Elenberg et al., 2017], and high dimensional sparse regression problems…”
Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection (2020, unknown): “However, our problem 1 is not sub-modular, and the (weak) sub-modular analysis (Das & Kempe, 2011) can only bound the ratio between L [ f S n ] and the best loss of subnetworks of size n achieved by (1), not the best loss L ∗ N achieved by the best convex combination of all the N neurons in the…”
SpeedBoost: Anytime Prediction with Uniform Near-Optimality (2012, methodology): “7 in [2], we have z′(L ∪ hj) ≥ λminz ′(L ∪ hj).”
Influence Maximization on Social Graphs: A Survey (2018, background): “The weakly submodular functions [114] are more general to model real applications compared to the predominate monotone submodular functions in the IM community.”
Submodular Maximization in Clean Linear Time (2020, background): “Similarly, nearly all aspects of the machine learning pipeline involve discrete tasks, from data summarization [47] and sketching [55] to feature selection [11] and model explanation [58].”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, methodology): “It is deﬁned as (equivalent to that in Zhou & Spanos (2016)): min which is closely related to the submodularity ratio by Das & Kempe (2011).”
ProtoDash: Fast Interpretable Prototype Selection (2017, methodology): “The submodularity ratio [6] of L with respect to (w.”
Restricted Strong Convexity Implies Weak Submodularity (2016, methodology): “[1] considers the specific case of maximizing R(2) objective.”
Submodularity in Data Subset Selection and Active Learning (2015, background): “…for an underlying task (Shinohara, 2014; Zheng et al., 2014; Hoi et al., 2006; Shamaiah et al., 2010; Prasad et al., 2014; Krause et al., 2008; Das & Kempe, 2011; Wei et al., 2014b; Kempe et al., 2003; Gabillon et al., 2013; Chen & Krause, 2013; Reed & Ghahramani, 2013; Singla et al., 2014;…”