Reusable Influence Screening for Threshold Search in Robust Submodular Selection

Many robust selection problems ask for a small set that does well under the worst of many scenarios. Examples include placing sensors so the slowest-detected contamination event is still caught quickly, or picking stations so the worst-predicted location is still predicted well. The standard method, SATURATE, avoids optimizing the badly behaved worst-case objective directly. Instead it binary-searches over a target value $c$. For each guess it caps every scenario's score at $c$, averages the capped scores, and runs a greedy cover to see whether $c$ is reachable within budget. Each guess repeats a full greedy pass over every candidate and every scenario. On a network like the Battle of Water Sensor Networks, with 12,527 candidate nodes and 3,424 scenarios, that repetition is the cost.

This note proposes using influence-based variable reduction to shrink the candidate set that each threshold test must consider. Influence-based variable reduction is the theory of approximating a function on many binary inputs by a "junta," a function that depends on only a few of them. The proposal rests on two plain facts. First, an element's influence on the capped objective can never decrease as the cap $c$ rises. A candidate that is unimportant at the current upper end of the search interval is therefore unimportant at every threshold the search will still visit, so one screening stays valid and only gets tighter as the search narrows. Second, influences under random sets have an exact correlation form. One batch of objective evaluations on random sets yields influence estimates for every element, every scenario, and every threshold, with no further calls to the objective. The open scientific question is how the number of elements that matter grows with the target. The open engineering question is whether this beats the obvious acceleration, lazy greedy evaluation.

Core Claim

Write $F_i$ for the monotone submodular score of scenario $i$. Submodular means adding an item helps less when the set is already larger. The capped score is $\hat F_{i,c}(A)=\min(F_i(A),c)$. Draw random sets $R$ by including each element independently with probability $p$, chosen near the solution density $\alpha k/n$. The $p$-biased influence of element $e$ on the capped score is its expected marginal gain against such a random background. It can be computed from plain evaluations, without per-element queries, via the standard $p$-biased identity

$$\mathrm{Inf}^{(p)}_{e}(\hat F_{i,c}) \;=\; \mathbb{E}_R\big[\hat F_{i,c}(R\cup e)-\hat F_{i,c}(R\setminus e)\big] \;=\; \frac{\mathbb{E}_R\big[\hat F_{i,c}(R)\,(\mathbf 1[e\in R]-p)\big]}{p(1-p)}.$$

The right-hand side is a degree-one Fourier coefficient. It is estimated for all $n$ elements at once from $S$ sampled pairs $(R_s, F_i(R_s))$, which costs $S\cdot m$ objective evaluations in total, where $m$ is the number of scenarios. Because $\min(F_i(R_s),c)$ can be recomputed for any $c$ from the stored value, the same samples serve every threshold the binary search visits.

The left-hand form shows that each marginal gain $\min(F_i(A\cup e),c)-\min(F_i(A),c)$ is nondecreasing in $c$. Hence each influence is nondecreasing in $c$. Binary search queries always lie below the current upper bound $c_{hi}$, and $c_{hi}$ only falls. A screen computed at $c_{hi}$ is therefore conservative for every later query, and the retained set shrinks monotonically over the search.

The claim is that screening by these threshold-dependent, per-scenario influences can cut objective evaluations several-fold beyond lazy greedy on large instances while keeping the worst-case objective unchanged. A cheap diminishing-returns check after each threshold test keeps any error from pruning bounded and visible.

Relation to Prior Work

The method's outer loop comes from Selecting Observations against Adversarial Objectives. That paper introduced the binary search over $c$, the truncation trick that restores submodularity, and the $\alpha k$ budget relaxation. It evaluates all ground elements at every greedy step of every threshold test. We keep its search and its guarantee structure and change only which candidates the inner cover considers. Algorithms and Hardness for Active Learning on Graphs pairs a threshold search with a submodular max-flow surrogate. Its authors note that repeated max-flows become prohibitive on very large graphs. That is the same bottleneck in a second setting, and we treat it as a secondary test bed rather than the core.

Three papers motivate the expectation that few elements matter. Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas and Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions show that submodular functions are approximated by juntas and concentrate on low-degree Fourier terms. Learning Coverage Functions and Private Release of Marginals shows that coverage functions, the shape of sensor-detection objectives, depend essentially on few variables. These results concern average-case approximation under a fixed distribution, not worst-case optimization. They justify screening as a hypothesis; they do not guarantee it. That gap is why the proposal includes a correctness check rather than relying on approximation theory.

Two papers supply estimation technique. Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression shows that a stochastic Fourier estimator under non-uniform distributions runs in time linear in sample size. We use its degree-one, square-loss form for $p$-biased influence estimation. Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism introduces $p$-subset influence and casts relevant-variable discovery as submodular minimization with sampled oracles. It never couples this to a search over objective values, which is the coupling we add.

Finally, Testing Junta Truncation studies distributions conditioned on a junta and treats truncation as a statistical object. We instead truncate the objective and ask how its relevant-variable set $k(c)$ moves with the cap. To our knowledge no paper in the file measures that quantity.

Research Program

The algorithm has three parts, plus one deliberate design choice.

The first part is sampling. Before the search, draw $S$ random sets and store all $F_i(R_s)$.

The second part is screening at each threshold $c$. Compute per-scenario influence estimates from the stored samples, and retain an element if its influence exceeds $\eta$ times the remaining deficit $c-\mathbb{E}[\hat F_{i,c}]$ for at least one scenario $i$. Keeping the union over scenarios, rather than screening on the averaged objective, is the deliberate choice. An element that serves only one lagging scenario has averaged influence near $1/m$ and would be wrongly dropped, even though that scenario is exactly what the max-min objective cares about.

The third part is the inner cover. Run SATURATE's greedy partial cover, with lazy evaluation, on the retained set $U$.

After the cover stops at set $A$, the dropped elements are checked once at $A$. By submodularity, an element whose capped gain at $A$ is at most $\delta$ adds at most $\delta$ to any superset of $A$. If every dropped element passes, then completing $A$ with any $j$ dropped elements adds at most $j\delta$. Elements that fail are added back and the cover resumes.

This certificate is weaker than SATURATE's full guarantee. It bounds what pruning could have cost at the final set, not along the greedy path. A theoretical aim is to find conditions, for instance coverage functions with bounded element frequencies, under which screened greedy provably retains the $\alpha$ bound. We do not expect screening to remove the budget relaxation; the file's own hardness results argue against that.

The analytical deliverable is the curve $k(c)$, the number of retained elements as a function of the cap, on each benchmark. Monotonicity predicts that this curve is nondecreasing. Its shape decides everything practical. If $k(c)$ stays far below $n$ near the optimal threshold, screening pays. If it approaches $n$, screening is useless exactly where the search spends its final steps.

Baselines

The naive reference is SATURATE as published in Selecting Observations against Adversarial Objectives, run on the full ground set with plain greedy. It fixes the target solution quality. On Michaelis-Menten robust design the paper reports 69% efficiency for SATURATE against 52% for semidefinite programming. On Pacific Northwest precipitation it reports SATURATE running 5–10x faster than simulated annealing at matching or better quality. On BWSN the file gives no reported numerical result, so our full-SATURATE run will establish the reference.

The strongest competitor is SATURATE with lazy greedy evaluation, which keeps a priority queue of stale upper bounds on marginal gains and re-evaluates only the top candidate. We additionally carry singleton bounds across thresholds, which monotonicity makes valid when moving downward. It is the strongest competitor because it attacks the same cost, repeated marginal-gain evaluation, with no estimation error. It will share our code, evaluation oracle, binary search tolerance, and budget relaxation. Our method beats it only if it reaches the same $\min_i F_i(A)$, within 1% relative, with clearly fewer total scenario evaluations and less wall time once the screening samples are counted. We target at least a 3x reduction on BWSN.

The key-ingredient ablation is singleton screening, the $p\to 0$ limit of our influence, which ranks elements by capped singleton value. This isolates whether background context matters. Singleton value cannot see redundancy among adjacent sensors; $p$-biased influence can. A second ablation screens on the averaged capped objective instead of the per-scenario union. If it degrades the worst case, that confirms the role of the union.

The third ablation is random candidate subsampling to the same retained-set size, with the same certificate and add-back loop.

Tuning parity matters for all methods. $\eta$, $\delta$, $S$ and $p$ are tuned on Pacific Northwest precipitation only, then frozen for BWSN and Michaelis-Menten. Lazy SATURATE has no comparable knobs to tune, so we report our method across a small grid of $\eta$ as well as at the frozen setting.

Why not just…?

Why not just use lazy greedy inside SATURATE? This is the real threat, and the proposal is built to lose to it visibly if screening adds nothing. Lazy evaluation already skips most re-evaluations within one cover. But every new threshold restarts from the empty set, so each cover begins with a full round over all $n$ elements, and every evaluation costs $m$ scenario calls. Screening removes elements before that round and reuses one sample batch across all thresholds. Whether this matters is an empirical question settled by the BWSN oracle-call comparison. If lazy SATURATE is within a factor of 1.5 of the screened version, we will report screening as unnecessary at this scale.

Why not just subsample candidates at random, as stochastic greedy methods do? Random subsampling is cheap and unbiased on average. However, the max-min objective is driven by rare elements that rescue a lagging scenario, and uniform sampling drops those at the same rate as redundant ones. The equal-size random-subsampling ablation, scored on worst-case objective and on how many add-backs the certificate triggers, measures this directly.

Why not just screen by each element's capped singleton value? Singleton values are exact, cost one pass, and upper-bound every later marginal gain, so they are the natural safe screen. Their weakness is redundancy: two neighboring sensors each have high singleton value but little value given the other. That makes the screen loose, and loose screens retain too much. The singleton ablation tests whether $p$-biased influence retains materially fewer elements at equal final quality. If it does not, the Fourier machinery is unnecessary.

Why not skip the threshold search and run greedy, or annealing, on the worst-case objective? Selecting Observations against Adversarial Objectives shows that greedy on $\min_i F_i$ can perform arbitrarily badly and that SATURATE matches tuned annealing at 5–10x lower cost. On graphs, Algorithms and Hardness for Active Learning on Graphs reports 1.0 for its threshold method against 0.076 for the leading heuristic on ego-Facebook at $k=10$. We include greedy-on-min only as a sanity floor.

Proposed Experiments

The main benchmark is BWSN, with 12,527 nodes and 3,424 scenarios, where the objective is worst-case detection time. Pacific Northwest precipitation (167 stations, maximum marginal Gaussian-process variance) serves as the small tuning instance. Michaelis-Menten robust design checks that screening does not break SATURATE's 69% efficiency. We report, at budgets $k\in\{5,10,20,50\}$: worst-case objective; total scenario evaluations including screening samples; wall time; number of binary search steps; and retained-set size and add-back count per threshold.

As a secondary transfer test, we screen candidate nodes before the flow-gadget greedy of Algorithms and Hardness for Active Learning on Graphs on ca-GrQc and ego-Facebook. This test asks whether fewer max-flow computations suffice at equal cut-sparsity ratio. Because cut sparsity is not submodular, the certificate does not carry over, and we will report that test as purely empirical.

Three outcomes decide the proposal. The first is the measured $k(c)$ curve on BWSN near the optimal threshold. A retained fraction above roughly one half means screening cannot pay, and we stop. The second is the head-to-head against lazy SATURATE with carried bounds, at equal worst-case objective. The third is the singleton-screening ablation, which shows whether influence measured against random backgrounds, the specifically junta-theoretic ingredient, is what does the work. We will also report estimator error against exact marginal gains on a random subset of elements, as a function of $S$ and $p$. Small $p$ inflates the variance of the correlation estimator, and that variance could erase the savings.