Scalable Greedy Feature Selection via Weak Submodularity

Abstract

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.

To appear in AISTATS 2017

References in corpus (12)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• Maximization of Approximately Submodular Functions
• Greedy Column Subset Selection: New Bounds and Distributed Algorithms

Cited by in corpus (16)

• Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
• Resilient Non-Submodular Maximization over Matroid Constraints
• Robust Maximization of Non-Submodular Objectives
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Near-Optimal Sparse Sensing for Gaussian Detection with Correlated Observations
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
• GRACE: Generating Concise and Informative Contrastive Sample to Explain Neural Network Model's Prediction
• Flexible Modeling of Diversity with Strongly Log-Concave Distributions
• Scalable Algorithms for the Sparse Ridge Regression
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization
• Controlled Islanding via Weak Submodularity
• Efficient Processing of k-regret Minimization Queries with Theoretical Guarantees
• Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling
• Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
• Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression