Submodular Function Maximization

By Andreas Krause, D. Golovin. 2014

1,070 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
Anchors: High-Precision Model-Agnostic Explanations (2018, methodology): “We use an iterative, greedy method that provides guarantees on the quality of our solution, due to the submodular nature of the optimization (Krause and Golovin 2014).”
Maximizing acquisition functions for Bayesian optimization (2018, methodology): “We assessed the efﬁcacy of gradient-based and submodular strategies for maximizing acquisition function in two primary settings: “synthetic”, where task f was drawn from a known GP prior, and “black-box”, where f ’s nature is unknown to the optimizer.”
Towards Further Automation in AutoML (2018, methodology): “Our base strategy for portfolio building is greedy submodular function minimization (Krause and Golovin, 2014), which has already been successfully applied to combinatorial optimization (Xu et al., 2010, 2011; Seipp et al., 2015).”
Adaptive Information Gathering via Imitation Learning (2017, background): “Problem 1 is a set function maximization problem which in general can be NP-Hard (Krause and Golovin [23]).”
Practical Automated Machine Learning for the AutoML Challenge 2018 (2018, background): “…iteration of Hyberband in the competition’s very tight budget and rather wanted to maximize the number of evaluated configurations. minimization (Krause and Golovin, 2014) w.r.t. the normalized regret across all datasets in this matrix to obtain a portfolio of machine learning pipelines (see…”
A tutorial on Gaussian process regression: Modelling, exploring, and exploiting functions (2016, background): “This is based on two properties of the acquisition function called submodularity and monotonicity (Krause and Golovin, 2012).”
Some Submodular Data-Poisoning Attacks on Machine Learners (2015, methodology): “First, we brieﬂy review submodular function maximization [8].”
Deep Metric Learning via Facility Location (2016, background): “Maximizing equation 4 with respect to subset S is NP-hard, but there is a well established worst case optimality bound of O ( 1− 1e ) for the greedy solution of the problem via submodularity [17].”
Video summarization by learning submodular mixtures of objectives (2015, background): “For more information on submodular function maximization we refer the reader to [14].”
Semantically Equivalent Adversarial Rules for Debugging NLP models (2018, background): “While Eq (3) is NP-hard, the objective is monotone submodular (Krause and Golovin, 2014), and thus a greedy algorithm that iteratively adds the rule with the highest marginal gain offers a constantfactor approximation guarantee of 1 − 1/e to the optimum.”
Submodular Maximization in Clean Linear Time (2020, methodology): “, n}, we use the monotone and submodular facility location function [38]”
Learning Where to Look: Data-Driven Viewpoint Set Selection for 3D Scenes (2017, methodology): “We next prove that this optimization is tractable, even at the scale of millions of images, by exploiting the submodular maximization approaches described in Krause et al [18].”