Submodular Maximization with Predictions: The Exact Price of Error

Maximizing a monotone submodular function under a cardinality constraint $K$ has a classical approximation guarantee, but in many subset-selection tasks the objective cannot be evaluated while the set is chosen, and an algorithm maximizes a learned model of the objective, a surrogate. Prior work bounds the surrogate's error on function values and is pessimistic: no algorithm with polynomially many queries retains a constant fraction of the optimum. The classical greedy guarantee rests on marginal gains, and we measure the error there: the surrogate may distort any marginal gain by at most a factor $\eta$. We consider deterministic algorithms that query only the surrogate and determine three prices. The information price is $1/\eta$: with unlimited queries, no deterministic algorithm guarantees more, and exhaustive search on the surrogate attains it. Predictive greedy, the greedy algorithm applied to the surrogate, pays exactly ${\rho }_K(\eta )$, an explicit function of $\eta$ and $K$ that tends to $1-e^{-1/\eta }$; the classical approximate-greedy bound is not tight for a surrogate. The price of the budget accounts for the rest: within greedy's query budget, no deterministic algorithm guarantees more than ${\rho }_K(\eta )$, so predictive greedy is optimal there. The error along the greedy path gives a per-instance guarantee and, on learned surrogates for feature selection, influence maximization, and summarization, ranks surrogates by their true performance.