Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics

Aranyak Mehta, Uri Nadav, Alexandros Psomas, Aviad Rubinstein

Abstract

In many real-world scenarios, such as auction design or search engine optimization, one must select a subset of $k$ items from $n$ candidates to maximize the expected value of the top-performing item. This task is complicated by the inherent uncertainty of candidate values, which are modeled as probability distributions. This paper explores the algorithmic complexity of maximizing expected order statistics. We prove that while the expected maximum (1st order statistic) admits a Polynomial Time Approximation Scheme (PTAS), the expected second-highest value is significantly harder to optimize. For distributions with a Monotone Hazard Rate (MHR), we demonstrate that a simple quantile-based scoring rule is both theoretically sound and empirically effective.

Introduction

Imagine running a high-stakes procurement auction or a search engine. Due to constraints like latency or evaluation costs, you can only perform a deep dive on a small subset of $k$ candidates. The goal is to select this subset such that the expected value of the eventual winner (the 1st order statistic) or the expected revenue (the 2nd order statistic in a second-price auction) is maximized.

A common pitfall is selecting candidates based solely on their mean values. However, a candidate with a lower mean but higher variance might be more likely to "hit a high note"—providing a spectacular maximum value that outweighs a "safer" candidate. This paper investigates how to navigate this trade-off between average performance and potential peaks through rigorous complexity analysis and practical heuristics.

Complexity and Algorithmic Approaches

The authors establish that the selection problem is NP-hard for both the 1st and 2nd order statistics. However, the structural properties of these objectives differ significantly, leading to different algorithmic possibilities.

The Expected Maximum (1st Order Statistic)

The expected maximum is a submodular function, which allows for efficient approximation. The paper introduces a Polynomial Time Approximation Scheme (PTAS) for this case. The scheme involves rounding values into discrete bins, discarding negligible tail contributions, and using a core-tail decomposition to reduce the search space to a manageable size. This ensures that for any fixed error tolerance, a near-optimal subset can be found in polynomial time.

The 2nd-Highest Value and the MHR Assumption

Maximizing the expected second-highest value is fundamentally more difficult, showing connections to the "Densest $k$-subgraph" problem. Under the Planted Clique Hypothesis, achieving a constant-factor approximation in polynomial time is impossible for general distributions.

To overcome this, the authors focus on distributions with a Monotone Hazard Rate (MHR), such as Normal, Exponential, and Uniform distributions. The MHR condition ensures that the tails of the distributions are well-behaved. For MHR distributions, they propose a simple Quantile-Based Scoring Rule: calculate the value of the $1/\sqrt{k}$ top quantile for each variable and select the top $k$ candidates.

Figure 2: Performance of the Quantile algorithm as a function of the chosen quantile compared to Greedy and Expectation baselines for k=10.

Empirical Evaluation

The proposed methods were tested on both synthetic and real-world data to validate the theoretical findings.

Synthetic Experiments

Using Normal distributions with randomized parameters, the authors compared the quantile rule against greedy optimization and simple expectation-based selection. As shown in Figure 2, the performance of the quantile algorithm is sensitive to the choice of quantile but reaches near-optimal levels (matching the Greedy approach) at high quantiles, significantly outperforming simple mean-based selection.

Real-World Application: Twitter Dataset

The methods were also applied to a dataset of 8 million tweets to predict and maximize the number of "likes." Models were trained using quantile loss to estimate the "high notes" directly from features. The results demonstrated that optimizing for the peak (the quantile) leads to much better subsets than standard regression-based selection.

Figure 1: Comparison of different selection strategies showing the true expected maximum achieved and the composition of the selected subset.

Key Insights

  • Submodularity of the Maximum: The diminishing returns property of the expected maximum makes it computationally tractable via a PTAS, unlike the second-highest value.
  • The Power of Quantiles: Under the MHR assumption, a single quantile score can effectively approximate both the 1st and 2nd order statistics. This provides a robust, easy-to-implement alternative to complex optimization.
  • Beyond the Mean: Standard regression (minimizing squared loss) often fails in subset selection because it optimizes for the average rather than the peak. Training for specific quantiles leads to significantly better outcomes in practice, as it identifies candidates with high upside potential.

Conclusion

While maximizing the "best of $k$" is theoretically complex, simple rules-of-thumb like quantile scoring perform remarkably well for common distributions. The gap between theoretical approximation factors and empirical performance suggests that these simple rules are even more powerful than currently proven. Future work remains in refining these constants and extending the results to scenarios where candidate values are correlated.

Summary updated

BibTeX
@inproceedings{mehta2020hitting,
  author = {Aranyak Mehta and Uri Nadav and Alexandros Psomas and Aviad Rubinstein},
  title = {{Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=MBfIq0QlVQ},
}
Figure