Near-Optimal Sample Complexity for PAC Submodular Maximization

How many noisy observations are needed to select a high-quality set with high probability? We study monotone submodular maximization, where an item's benefit can decrease as other items are selected. Given $n$ items and a selection budget $k$, we provide a polynomial-time algorithm that returns a set of value at least $(1-1/e){\mathrm{OPT}}_k-\epsilon$ with probability $1-\delta$, where ${\mathrm{OPT}}_k$ is the optimal value. Under independent unit-variance Gaussian noise on marginal gains, the algorithm uses $\tilde{O}(n{k}^2/{\epsilon }^2)$ observations, without knowing ${\mathrm{OPT}}_k$ or an upper bound on function values. A matching worst-case lower bound, up to logarithmic factors, holds even for additive functions, for fixed $\delta \le 0.05$ and $1\le k\le n/8$. The algorithm begins by evaluating each item and then selects from random candidate subsets. An exponential-moment bound for sample maxima controls the total loss from these subsets; the initial gain and the slack in the greedy guarantee together offset that loss. With exact marginal queries, the same analysis gives the strict $1-1/e$ ratio with high probability using $O(n\log (k/\delta ))$ queries. We further show that, at comparable optimal values, submodular maximization can require polynomially more observations than maximizing an additive function.