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 Ω(n/k) query lower bound for approximating to within any constant factor. We strengthen their lower bound to a nearly tight Ω(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 O(n/k) queries, and that this is tight up to polylog factors.