Two-Stage Greedy

An approach that switches between two optimizers midway through.

The two-stage greedy optimizer is a general purpose framework for combining two optimizers by making the first \(n\) selections out of \(k\) total selections using one optimizer, and then making the remainder using the other. When the first optimizer is random selection and the second approach is naive/lazy greedy, this becomes partial enumeration. By default, the first algorithm is the naive greedy optimizer and the second algorithm is the lazy greedy. This combination results in the same selection as either optimizer individually but replaces the computationally intensive first few steps for the priority queue, where the algorithm may require scanning through almost the entire queue, with the parallelizable naive greedy algorithm. While, in theory, the lazy greedy algorithm will never perform more function calls than the naive greedy algorithm, there are costs associated both with maintaining a priority queue and with evaluating a single example instead of a batch of examples.

This optimizer, with the naive greedy optimizer first and the lazy greedy optimizer second, is the default optimizer for apricot selectors.

param self.function:  A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized. type self.function:  base.BaseSelection param self.n_first_selections:  The number of selections to perform using the naive greedy algorithm before populating the priority queue and using the lazy greedy algorithm. type self.n_first_selections:  int param self.verbose:  Whether to display a progress bar during the optimization process. type self.verbose:  bool

self.function

A submodular function that implements the _calculate_gains and _select_next methods. This is the function that will be optimized.

Type:base.BaseSelection

self.verbose

Whether to display a progress bar during the optimization process.

Type:bool