Fast Parallel Algorithms for Feature Selection

By Sharon Qian, Yaron Singer. 2019

8 citations recorded by the source corpus.

In this paper, we propose a new framework for designing fast parallel algorithms for fundamental statistical subset selection tasks that include feature selection and experimental design. Such tasks are known to be weakly submodular and are amenable to optimization via the standard greedy algorithm. Despite its desirable approximation guarantees, however, the greedy algorithm is inherently sequential and in the worst case, its parallel runtime is linear in the size of the data. Recently, there has been a surge of interest in a parallel optimization technique called adaptive sampling which produces solutions with desirable approximation guarantees for submodular maximization in exponentially faster parallel runtime. Unfortunately, we show that for general weakly submodular functions such accelerations are impossible. The major contribution in this paper is a novel relaxation of submodularity which we call differential submodularity. We first prove that differential submodularity characterizes objectives like feature selection and experimental design. We then design an adaptive sampling algorithm for differentially submodular functions whose parallel runtime is logarithmic in the size of the data and achieves strong approximation guarantees. Through experiments, we show the algorithm's performance is competitive with state-of-the-art methods and obtains dramatic speedups for feature selection and experimental design problems.

Subfields: Artificial Intelligence, Algorithms & Complexity

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 Algorithms & Complexity

Citations in the corpus

Causal Mediation Analysis for Interpreting Neural NLP: The Case of Gender Bias (2020, methodology): “For non-monotone or non-submodular functions, there are parallelized algorithms that use similar techniques to select sets (Balkanski et al., 2018; Qian and Singer, 2019; Fahrbach et al., 2019a).”
Investigating Gender Bias in Language Models Using Causal Mediation Analysis (2020, methodology): “For non-monotone or non-submodular functions, there are parallelized algorithms that use similar techniques to select sets (Balkanski et al., 2018; Qian and Singer, 2019; Fahrbach et al., 2019a).”
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).”