Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies
Shlomi Weitzman Sivan Sabato
We study adaptive combinatorial maximization, which is a core challenge in
machine learning, with applications in active learning as well as many other
domains. We study the Bayesian setting, and consider the objectives of
maximization under a cardinality constraint and minimum cost coverage. We
provide new comprehensive approximation guarantees that subsume previous
results, as well as considerably strengthen them. Our approximation guarantees
simultaneously support the maximal gain ratio as well as near-submodular
utility functions, and include both maximization under a cardinality constraint
and a minimum cost coverage guarantee. In addition, we provided an
approximation guarantee for a modified prior, which is crucial for obtaining
active learning guarantees that do not depend on the smallest probability in
the prior. Moreover, we discover a new parameter of adaptive selection
policies, which we term the "maximal gain ratio". We show that this parameter
is strictly less restrictive than the greedy approximation parameter that has
been used in previous approximation guarantees, and show that it can be used to
provide stronger approximation guarantees than previous results. In particular,
we show that the maximal gain ratio is never larger than the greedy
approximation factor of a policy, and that it can be considerably smaller. This
provides a new insight into the properties that make a policy useful for
adaptive combinatorial maximization.