Lazier Than Lazy Greedy

Given a set of items \(V = \{1, 2, 3, \cdots, n\}\) which we also call the Ground Set, define a utility function (set function) \(f:2^V \rightarrow \Re\), which measures how good a subset \(X \subseteq V\) is. Let \(c :2^V \rightarrow \Re\) be a cost function, which describes the cost of the set (for example, the size of the subset). The goal is then to have a subset \(X\) which maximizes \(f\) while simultaneously minimizing the cost function \(c\). It is easy to see that maximizing a generic set function becomes computationally infeasible as \(V\) grows. Often the cost \(c\) is budget constrained (for example, a fixed set summary) and a natural formulation of this is the following problem:

\[\max\{f(X) \mbox{ such that } c(X) \leq b\}\]

For any SetFunction, lazier-than-lazy greedy maximization can be achieved by calling maximize() with optimizer=’LazierThanLazyGreedy’. The implementation of lazier-than-lazy greedy optimizer in this library is an implementation of “random sampling with lazy evaluation” proposed by [MBK+15]. It combines both stochastic greedy and lazy greedy approaches. Essentially, in every iteration, it applies lazy greedy for finding the best element from a random sub sample of the remaining ground set and adds that element to the greedy set. Such an element is added in every iteration until the desired budget (budget) is achieved or the best gain in any iteration is zero (stopIfZeroGain) or negative (stopIfNegativeGain).

Note

For submodular functions, LazierThanLazyGreedy optimizer is the most efficient, followed by StochasticGreedy, LazyGreedy and NaiveGreedy in the descending order of speed.