Diversification as Risk Minimization

• URL: http://arxiv.org/abs/2510.22681v1
• Date: Sun, 26 Oct 2025 13:51:45 GMT
• Title: Diversification as Risk Minimization
• Authors: Rikiya Takehi, Fernando Diaz, Tetsuya Sakai,
• Abstract summary: We show that diversification algorithms are no more robust than a naive, non-diversified algorithm.<n>We introduce VRisk, which measures the expected risk faced by the least-served fraction of intents in a query.<n>We then propose VRisker, a fast greedy re-ranker with provable approximation guarantees.
• Score: 55.503117695676416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Users tend to remember failures of a search session more than its many successes. This observation has led to work on search robustness, where systems are penalized if they perform very poorly on some queries. However, this principle of robustness has been overlooked within a single query. An ambiguous or underspecified query (e.g., ``jaguar'') can have several user intents, where popular intents often dominate the ranking, leaving users with minority intents unsatisfied. Although the diversification literature has long recognized this issue, existing metrics only model the average relevance across intents and provide no robustness guarantees. More surprisingly, we show theoretically and empirically that many well-known diversification algorithms are no more robust than a naive, non-diversified algorithm. To address this critical gap, we propose to frame diversification as a risk-minimization problem. We introduce VRisk, which measures the expected risk faced by the least-served fraction of intents in a query. Optimizing VRisk produces a robust ranking, reducing the likelihood of poor user experiences. We then propose VRisker, a fast greedy re-ranker with provable approximation guarantees. Finally, experiments on NTCIR INTENT-2, TREC Web 2012, and MovieLens show the vulnerability of existing methods. VRisker reduces worst-case intent failures by up to 33% with a minimal 2% drop in average performance.

Related papers

• Sample Smart, Not Hard: Correctness-First Decoding for Better Reasoning in LLMs [72.82403830490084]
  We argue that the decoding rule should be calibrated by correctness, not confidence alone.<n>We propose simple strategies that achieve this goal: Greedy-Threshold makes sampling greedy at very low confidence steps.<n>Together, our findings challenge prevailings about decoding under uncertainty and show gains across math and general reasoning benchmarks.
  arXiv  Detail & Related papers  (2025-10-07T14:46:12Z)
• Achievable distributional robustness when the robust risk is only partially identified [8.192907805418583]
  In safety-critical applications, machine learning models should generalize well under worst-case distribution shifts.<n>We introduce the worst-case robust risk as a new measure of robustness that is always well-defined regardless of identifiability.<n>First, we show that existing robustness methods are provably suboptimal in the partially identifiable case.
  arXiv  Detail & Related papers  (2025-02-04T20:42:47Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• FasterRisk: Fast and Accurate Interpretable Risk Scores [17.015744876065195]
  Risk scores are sparse linear models with integer coefficients. Recent work used mathematical programming, which is computationally slow. We introduce an approach for efficiently producing a collection of high-quality risk scores learned from data.
  arXiv  Detail & Related papers  (2022-10-12T00:36:01Z)
• Few-shot Forgery Detection via Guided Adversarial Interpolation [56.59499187594308]
  Existing forgery detection methods suffer from significant performance drops when applied to unseen novel forgery approaches. We propose Guided Adversarial Interpolation (GAI) to overcome the few-shot forgery detection problem. Our method is validated to be robust to choices of majority and minority forgery approaches.
  arXiv  Detail & Related papers  (2022-04-12T16:05:10Z)
• Tightening the Approximation Error of Adversarial Risk with Auto Loss Function Search [12.263913626161155]
  A common type of evaluation is to approximate the adversarial risk of a model as a robustness indicator. We propose AutoLoss-AR, the first method for searching loss functions for tightening the error. The results demonstrate the effectiveness of the proposed methods.
  arXiv  Detail & Related papers  (2021-11-09T11:47:43Z)
• Online Sign Identification: Minimization of the Number of Errors in Thresholding Bandits [27.09804256642197]
  We introduce a large family of algorithms inspired by the Frank-Wolfe algorithm. We construct new explicit algorithms for a broad class of problems. We explain this phenomenon on an insightful toy problem.
  arXiv  Detail & Related papers  (2021-10-18T09:36:36Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise. First-order guarantees are relatively well understood in statistical and online learning. We show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees.
  arXiv  Detail & Related papers  (2021-07-05T19:20:34Z)
• Hidden Cost of Randomized Smoothing [72.93630656906599]
  In this paper, we point out the side effects of current randomized smoothing. Specifically, we articulate and prove two major points: 1) the decision boundaries of smoothed classifiers will shrink, resulting in disparity in class-wise accuracy; 2) applying noise augmentation in the training process does not necessarily resolve the shrinking issue due to the inconsistent learning objectives.
  arXiv  Detail & Related papers  (2020-03-02T23:37:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.