# Restricted Strong Convexity Implies Weak Submodularity

arXiv: https://arxiv.org/abs/1612.00804 · HTML: https://mlsanity.com/paper/1612.00804/

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Dec 2016.

## Built on by (most cited first, 30 of 52)

- [GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training](https://mlsanity.com/paper/2103.00123/) (2021)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Learning to Maximize Mutual Information for Dynamic Feature Selection](https://mlsanity.com/paper/2301.00557/) (2023)
- [Loss-Curvature Matching for Dataset Selection and Condensation](https://mlsanity.com/paper/2303.04449/) (2023)
- [TAGCOS: Task-agnostic Gradient Clustered Coreset Selection for Instruction Tuning Data](https://mlsanity.com/paper/2407.15235/) (2024)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Data-Efficient Structured Pruning via Submodular Optimization](https://mlsanity.com/paper/2203.04940/) (2022)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [FasterRisk: Fast and Accurate Interpretable Risk Scores](https://mlsanity.com/paper/2210.05846/) (2022)
- [Estimating Conditional Mutual Information for Dynamic Feature Selection](https://mlsanity.com/paper/2306.03301/) (2023)
- [Fast Sparse Classification for Generalized Linear and Additive Models](https://mlsanity.com/paper/2202.11389/) (2022)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [SPOT: A framework for selection of prototypes using optimal transport](https://mlsanity.com/paper/2103.10159/) (2021)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [ℓ_∞-Robustness and Beyond: Unleashing Efficient Adversarial Training](https://mlsanity.com/paper/2112.00378/) (2021)
- [Adversarial Coreset Selection for Efficient Robust Training](https://mlsanity.com/paper/2209.05785/) (2022)
- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [Robust Gaussian Processes via Relevance Pursuit](https://mlsanity.com/paper/2410.24222/) (2024)
- [OKRidge: Scalable Optimal k-Sparse Ridge Regression](https://mlsanity.com/paper/2304.06686/) (2023)
- [Sparse Bayesian Learning via Stepwise Regression](https://mlsanity.com/paper/2106.06095/) (2021)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [A Survey of Dataset Refinement for Problems in Computer Vision Datasets](https://mlsanity.com/paper/2210.11717/) (2022)
- [Submodular Framework for Structured-Sparse Optimal Transport](https://mlsanity.com/paper/2406.04914/) (2024)
- [Fast Feature Selection with Fairness Constraints](https://mlsanity.com/paper/2202.13718/) (2022)
- [Feature Space Sketching for Logistic Regression](https://mlsanity.com/paper/2303.14284/) (2023)
- [Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Dataset](https://mlsanity.com/paper/2502.18955/) (2025)
- [Feature Cross Search via Submodular Optimization](https://mlsanity.com/paper/2107.02139/) (2021)
- [Towards Efficient and Domain-Agnostic Evasion Attack with High-dimensional Categorical Inputs](https://mlsanity.com/paper/2212.06836/) (2022)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)

## Abstract (arXiv)

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.