Title: 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.