Comments on the proof of adaptive submodular function minimization
This is an incremental correction that affects researchers in active learning and stochastic optimization who rely on adaptive submodular function minimization results.
The paper identifies an error in Theorem 5 of a prior work on group-based active query selection, by presenting a counterexample to a key step in Theorem A.11 from a foundational paper on adaptive submodularity, which invalidates the proof of the expected query bound.
We point out an issue with Theorem 5 appearing in "Group-based active query selection for rapid diagnosis in time-critical situations". Theorem 5 bounds the expected number of queries for a greedy algorithm to identify the class of an item within a constant factor of optimal. The Theorem is based on correctness of a result on minimization of adaptive submodular functions. We present an example that shows that a critical step in Theorem A.11 of "Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization" is incorrect.