# Scalable Greedy Feature Selection via Weak Submodularity

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2017.

## Built on by (most cited first, 19 of 19)

- [RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning](https://mlsanity.com/paper/2106.07760/) (2021)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Greedy Modality Selection via Approximate Submodular Maximization](https://mlsanity.com/paper/2210.12562/) (2022)
- [Network Generalization Prediction for Safety Critical Tasks in Novel Operating Domains](https://mlsanity.com/paper/2108.07399/) (2021)
- [Generator Assisted Mixture of Experts For Feature Acquisition in Batch](https://mlsanity.com/paper/2312.12574/) (2023)
- [Active Few-Shot Fine-Tuning](https://mlsanity.com/paper/2402.15441/) (2024)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [E-LDA: Toward Interpretable LDA Topic Models with Strong Guarantees in Logarithmic Parallel Time](https://mlsanity.com/paper/2506.07747/) (2025)
- [Distributionally Robust Feature Selection](https://mlsanity.com/paper/2510.21113/) (2025)
- [Error-Correction for Sparse Support Recovery Algorithms](https://mlsanity.com/paper/2103.03801/) (2021)
- [Multihop: Leveraging Complex Models to Learn Accurate Simple Models](https://mlsanity.com/paper/2109.06961/) (2021)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [End-to-end Feature Selection Approach for Learning Skinny Trees](https://mlsanity.com/paper/2310.18542/) (2023)
- [Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapes](https://mlsanity.com/paper/2511.17399/) (2025)
- [Stochastic Sequential Search in Very-High-Dimensional Feature Selection](https://mlsanity.com/paper/2608.01502/) (2026)
- [Population-Robust Feature Selection via Generalized Welfare Optimization](https://mlsanity.com/paper/2608.02887/) (2026)

## Abstract (arXiv)

Greedy algorithms are widely used for problems in machine learning such as feature selection and set function optimization. Unfortunately, for large datasets, the running time of even greedy algorithms can be quite high. This is because for each greedy step we need to refit a model or calculate a function using the previously selected choices and the new candidate. Two algorithms that are faster approximations to the greedy forward selection were introduced recently ([Mirzasoleiman et al. 2013, 2015]). They achieve better performance by exploiting distributed computation and stochastic evaluation respectively. Both algorithms have provable performance guarantees for submodular functions. In this paper we show that divergent from previously held opinion, submodularity is not required to obtain approximation guarantees for these two algorithms. Specifically, we show that a generalized concept of weak submodularity suffices to give multiplicative approximation guarantees. Our result extends the applicability of these algorithms to a larger class of functions. Furthermore, we show that a bounded submodularity ratio can be used to provide data dependent bounds that can sometimes be tighter also for submodular functions. We empirically validate our work by showing superior performance of fast greedy approximations versus several established baselines on artificial and real datasets.