Restricted Strong Convexity Implies Weak Submodularity

By Ethan R. Elenberg, Rajiv Khanna, A. Dimakis, Sahand N. Negahban. 2016

165 citations recorded by the source corpus.

We connect high-dimensional subset selection and submodular maximization. Our results extend the work of Das and Kempe (2011) from the setting of linear regression to arbitrary objective functions. For greedy feature selection, this connection allows us to obtain strong multiplicative performance bounds on several methods without statistical modeling assumptions. We also derive recovery guarantees of this form under standard assumptions. Our work shows that greedy algorithms perform within a constant factor from the best possible subset-selection solution for a broad class of general objective functions. Our methods allow a direct control over the number of obtained features as opposed to regularization parameters that only implicitly control sparsity. Our proof technique uses the concept of weak submodularity initially defined by Das and Kempe. We draw a connection between convex analysis and submodular set function theory which may be of independent interest for other statistical learning applications that have combinatorial structure.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training, Mathematical Optimization

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

In Mathematical Optimization

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, methodology): “We extend the relation established in [Elenberg et al., 2016] between weak submodularity and RSC/RSM parameters to this case.”
Streaming Weak Submodularity: Interpreting Neural Networks on the Fly (2017, background): “This setup is known to be weakly submodular under mild data assumptions [Elenberg et al., 2016].”
Fast Parallel Algorithms for Feature Selection (2019, methodology): “For example, one such advantage is that the user can specify exactly how many features to select and avoid computing the regularization parameter (in the case of Lasso ), which is generally computationally hard Mairal & Yu (2012).”
Guarantees for Greedy Maximization of Non-submodular Functions with Applications (2017, background): “Recently, Elenberg et al. (2016) proved that if f ( x ) has L -restricted smoothness and m -restricted strong convexity, then the submodularity ratio of F ( S ) is lower bounded by m/L .”
Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (2019, methodology): “…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 [Elenberg et al., 2018].”
GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training (2021, methodology): “Since Fλ(X ) is approximately submodular (Das & Kempe, 2011), a greedy algorithm (Nemhauser et al., 1978; Das & Kempe, 2011; Elenberg et al., 2018) admits a (1− exp(−γ)) approximation guarantee.”
Efficient Data Representation by Selecting Prototypes with Importance Weights (2017, methodology): “We need to explicitly prove that the set function is still weakly submodular with the added non-negativity constraint and reestablish all the guarantees derived in [11] as their original arguments cannot be directly used.”
Submodular Maximization in Clean Linear Time (2020, background): “Submodular functions have attracted significant interest from the machine learning community, and have led to the development of algorithms with near-optimal solutions for a wide range of applications, including outbreak detection [52], graph cuts in computer vision [40], image and video summarizati”
Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (2018, background): “• Expressing learning problems such as feature selection using weakly submodular functions (Das & Kempe, 2008; Khanna et al., 2017; Elenberg et al., 2018; Qian & Singer, 2019).”
ProtoDash: Fast Interpretable Prototype Selection (2017, methodology): “On the technical side, one recent work that we leverage and extend with non-negativity constraints for our MMD objective is [7].”
Beyond Distributive Fairness in Algorithmic Decision Making: Feature Selection for Procedurally Fair Learning (2018, methodology): “Throughout this paper, we always use logistic regression with L2-regularization.”