Finding Most Influential Sets

Identifying _most influential sets_ (MIS) – size-$k$ subsets whose removal maximally changes a target estimand – is typically infeasible because it requires searching over $n$ choose $k$ subsets. For estimands with linear-fractional leave-set-out effects, we show that MIS selection reduces to a one-parameter sequence of top-$k$ problems. Dinkelbach's method yields an algorithm with $\mathcal{O}(n)$ cost per iteration and finite termination. For fixed residualized inputs, the algorithm returns a globally optimal set for the univariate ratio objective, including the oracle-residualized partial linear model. With estimated nuisance functions, uniform denominator and generated-score stability imply approximation to the first-order oracle orthogonal-score objective; exact set recovery follows under a separation condition. Simulations and applications show that the method recovers exact MIS that were previously computationally inaccessible.

Machine learning models and statistical estimates are only as reliable as the data behind them. A natural diagnostic question is whether a small group of observations has disproportionate influence on a result. Finding this group exactly is usually infeasible, because there are too many possible groups to check one by one. We show that, for a broad class of problems, this difficult search can be turned into a much simpler procedure: repeatedly ranking observations and selecting the top-ranked ones. This applies when the effect of removing a group can be written as a ratio, a structure that arises in many common statistical and machine learning settings. The resulting method can find the exact most influential group in milliseconds, even in large datasets. It avoids important failures of earlier approximation methods, which can miss groups that only become influential when removed together. We apply the method to randomized experiments, text similarity, and benchmark datasets, revealing small subsets of observations that drive changes in results.