Technical Summary: Flexible Inference for Winners with Conditional Validity

Problem Statement

In many empirical workflows, researchers select a set of top-performing options (winners) based on data-driven criteria—such as the largest estimated treatment effects, best model performance, or highest feature importance—and subsequently report effect estimates for these selected units. Because the same data is used for both selection and estimation, naive post-selection estimates suffer from the "winner's curse," leading to systematically overoptimistic results and confidence intervals with below-nominal coverage.

While existing literature offers solutions, they face significant trade-offs:

• Simultaneous/Marginal Inference: Methods guaranteeing validity averaged over all possible selection outcomes often fail to provide valid inference for the specific winners observed in a given dataset.
• Conditional Inference: Existing conditional approaches (e.g., the polyhedral method, data splitting) are often restricted to specific parametric models, tailored to specific selection rules, or produce intervals that are excessively wide and unstable, particularly when competitors are close.

The central challenge is to develop a method that provides conditional coverage guarantees (validity for the specific winners selected from the observed data) without sacrificing selection quality or producing unreasonably wide intervals, while remaining applicable to nonparametric settings.

Methodology

The authors propose a flexible conditional inference method based on a data-adaptive exponential randomization scheme. The core idea is to replace the deterministic "hard" selection rule (selecting the top-$k$ items with the highest scores) with a randomized selection rule that samples winners according to a probability distribution proportional to their scores.

1. Randomized Selection Scheme

Instead of deterministically selecting the set $E^*$ that maximizes the score $s_E(T)$, the method samples a set of winners $\hat{E}$ from the collection of all $k$-subsets $\mathcal{E}_k$ using a discrete probability distribution:
$$P[\hat{E} = E \mid T = t] = \frac{\exp\left(\frac{s_E(t)}{\tau \cdot \sigma_s(t)}\right)}{\sum_{E' \in \mathcal{E}_k} \exp\left(\frac{s_{E'}(t)}{\tau \cdot \sigma_s(t)}\right)}$$
where:

• $s_E(t)$ is the additive score of subset $E$ given data $t$.
• $\sigma_s(t)$ is the dispersion of scores across all subsets, ensuring scale invariance.
• $\tau$ is a temperature parameter controlling the level of randomization.

Tuning-Free Calibration: The paper introduces a notion of regret to calibrate $\tau$ without manual tuning. By setting a user-specified regret budget $q$ (the acceptable loss in selection quality relative to the standard top-$k$ rule), the temperature is determined automatically as $\tau \leq q / \log |\mathcal{E}_k|$. This ensures the randomized selection closely matches the standard top-$k$ rule while enabling valid inference.

2. Inference Workflow

Once a set of winners $E_o$ is observed, the method constructs valid conditional confidence intervals for the effects $\mu_{E_o}$. The workflow involves three steps:

1. Conditioning to Remove Nuisance Parameters: The authors identify sufficient statistics $T^\perp_{j_o}$ (orthogonal to the target parameter $\mu_{j_o}$) such that the conditional density of the target statistic $T_{j_o}$ given the selection event $\{\hat{E} = E_o\}$ and $T^\perp_{j_o}$ is free of nuisance parameters.
2. Closed-Form Conditional Density: A key theoretical contribution is that, due to the specific design of the exponential mechanism, the conditional selection probability $P[\hat{E} = E_o \mid T = t]$ is available in closed form. Unlike the polyhedral method, which requires characterizing the selection event as a polyhedron, this approach does not need an analytical description of the selection event. The conditional density is derived as:
   $$f(t \mid \hat{E}=E_o, T^\perp_{j_o}=t^\perp) \propto \phi(t; \mu_{j_o}, \sigma^2_{j_o}) \times \Lambda_{E_o}(t, t^\perp)$$
   where $\Lambda_{E_o}$ is the selection weight derived from the exponential mechanism.
3. Pivot Construction: A pivot is constructed by applying the probability integral transform to this conditional density. This pivot follows a Uniform(0,1) distribution conditional on the selection event, allowing for the construction of exact $p$-values and confidence intervals via inversion.

3. Asymptotic Theory

The method is extended to nonparametric settings where the selection statistics are asymptotically linear. Under mild regularity conditions (bounded score derivatives and asymptotic linear representation of statistics), the pivot is shown to be asymptotically valid. This allows the method to be applied to binary outcomes (A/B/n testing), ranking models (Bradley–Terry–Davidson), and nonparametric feature importance, even when the underlying data is not Gaussian.

4. Efficient Implementation

Computing the normalizing constant for the exponential mechanism involves summing over exponentially many subsets. The authors leverage the additive structure of the scores to express this sum as an elementary symmetric polynomial, which can be evaluated in $O(pk)$ time using dynamic programming. This enables efficient sampling and the calculation of selection weights for inference.

Key Results

The paper evaluates the proposed "Randomized PSI" method against three baselines: the standard top-$k$ rule with no correction, the "Polyhedral PSI" (conditional but often wide), and "Data Splitting" (conditional but loses selection quality).

1. Selection Quality: The proposed method achieves regret close to zero, selecting winners nearly as well as the standard top-$k$ rule. In contrast, data splitting incurs significantly higher regret because it uses only a subset of the data for selection.
2. Coverage: The method achieves nominal conditional coverage (e.g., 95%) for the selected winners. It outperforms marginal baselines (like "Zoom Correction") which fail to provide conditional validity.
3. Interval Length: The proposed method produces substantially shorter confidence intervals than the polyhedral approach. In Gaussian simulations, polyhedral intervals were found to be 496% longer in some settings. While data splitting produces similarly short intervals, it does so at the cost of poor selection quality.
4. Nonparametric Applicability: The method successfully handles non-Gaussian data (binary outcomes, paired comparisons, and black-box feature importance) by relying on asymptotic guarantees, whereas many existing conditional methods are restricted to Gaussian or specific parametric models.

Significance and Claims

The authors claim that their work fills critical gaps in the post-selection inference literature:

• Flexibility: The method is broadly applicable to nonparametric settings with asymptotically linear statistics, covering diverse applications like clinical trials, leaderboard model evaluation, and feature importance.
• Conditional Validity without Analytical Tractability: It provides exact (or asymptotically exact) conditional inference without requiring an analytical characterization of the selection event, a major limitation of previous conditional methods.
• Balanced Trade-offs: It resolves the tension between selection quality and inferential power. By using a tuning-free randomization scheme guided by regret, it ensures that gains in inferential power (shorter intervals) do not come at the expense of selecting suboptimal winners.
• Practical Utility: The method produces numerically stable, short intervals that are practically useful, unlike the often infinite or unstable intervals produced by existing conditional approaches when competitors are close.

The paper concludes that this randomization approach provides a promising framework for future research, not only for addressing the winner's curse but also for broader post-selection inference problems, including comparisons between winners and runners-up.