A Near Linear Query Lower Bound for Submodular Maximization

We revisit the problem of selecting $k$-out-of-$n$ elements with the goal of optimizing an objective function, and ask whether it can be solved approximately with sublinear query complexity. For objective functions that are monotone submodular, [Li, Feldman, Kazemi, Karbasi, NeurIPS'22; Kuhnle, AISTATS'21] gave an $\Omega(n/k)$ query lower bound for approximating to within any constant factor. We strengthen their lower bound to a nearly tight $\tilde{\Omega}(n)$. This lower bound holds even for estimating the value of the optimal subset. When the objective function is additive, we prove that finding an approximately optimal subset still requires near-linear query complexity, but we can estimate the value of the optimal subset in $\tilde{O}(n/k)$ queries, and that this is tight up to polylog factors.

This paper investigates how efficiently we can select the best subset of items (specifically, choosing k out of n items) to maximize a certain benefit or objective. It asks if we can do this by examining fewer items than it would normally take to check each one. For objective functions that exhibit a common property known as "monotone submodularity"—where adding an item helps less as more items are already selected—the authors show that achieving a good approximation still requires checking nearly all items. For simpler objective functions (additive ones, where each item's contribution is independent and straightforward), the authors show that  estimating just the value (or quality) of the optimal selection can be done with significantly fewer queries, and the paper precisely determines these limits