Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of identifying most influential sets (MIS) by transforming the problem into a manageable sequence of top-$k$ selections, significantly reducing computational complexity. By employing Dinkelbach's method, the authors present an algorithm that operates with $\mathcal{O}(n)$ cost per iteration, ensuring finite termination and optimal set recovery for specific linear-fractional estimands. Simulations demonstrate the algorithm's effectiveness in recovering exact MIS that were previously deemed computationally infeasible, highlighting its practical applicability in complex data scenarios.
Transforming the identification of influential sets into a linear-fractional optimization problem unlocks previously inaccessible computational solutions.
Identifying most influential sets (MIS) - size-$k$ subsets whose removal maximally changes a target estimand - is typically infeasible because it requires searching over $\binom{n}{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.