Algorithms for Average Regret Minimization

Sabine Storandt, Stefan FunkeAAAI 2019 · DOI

Introduction

The problem of selecting a representative subset from a large database is central to multi-criteria decision-making. Traditional approaches often focus on minimizing "maximum regret"—the dissatisfaction of the most unhappy user. However, this worst-case metric is sensitive to outliers and computationally difficult to approximate. This paper introduces Average Regret Minimization, shifting the focus to the overall satisfaction of the user base.

Problem Formulation: From Max to Average Regret

Consider a scenario where a store must select a small subset of laptops to display. Users have varying preferences for attributes like SSD capacity and RAM. A single ranking (e.g., by price) fails to satisfy diverse needs.

Multi-criteria preferences for items like laptops (SSD vs RAM) across a preference space $\alpha_1$.

Regret measures the loss in utility a user experiences when their most preferred item is not in the displayed subset. While Maximum Regret Minimization aims to bound the worst-case loss, Average Regret integrates this loss over the entire space of possible user preferences, providing a more robust measure of "social welfare."

Methodology: The Submodularity Breakthrough

The authors define "Average Happiness" as the complement of average regret. A key theoretical contribution of this work is the proof that average happiness is a monotone submodular function.

Submodularity allows the use of a simple greedy algorithm: iteratively selecting the item that provides the maximum marginal increase in total happiness. This approach guarantees a solution within $(1 - 1/e) \approx 63\%$ of the optimal happiness.

To implement this, the authors address the challenge of calculating "happiness volume"—the integral of the maximum utility over a preference simplex. They propose:

  1. Exact Computation: Utilizing duality transforms for precise geometric calculations, though this scales poorly with dimensionality ($d$).
  2. Sampling-based Heuristic: Discretizing the preference space to estimate the volume, which offers significant speedups with minimal loss in accuracy.

Key Results and Evaluation

The algorithms were tested on synthetic and real-world datasets, including weather, oceanographic (ElNino), and flight (AirData) statistics.

Performance comparison of Forward vs. Reverse Greedy algorithms.

Experimental results highlight several key findings:

  • Efficiency: The sampling heuristic processed a dataset of $10^6$ points in under a second, compared to over 20 minutes for exact methods.
  • Algorithm Comparison: The "Forward Greedy" approach consistently outperformed "Reverse Greedy" in both computational speed and the quality of the resulting subset, as shown in the convergence of regret values.
  • Scalability: The methods effectively handle datasets with millions of records and up to 7 dimensions.

Conclusion and Future Work

By leveraging submodularity, this paper provides a theoretically sound and practically efficient framework for average regret minimization. While the "curse of dimensionality" remains a challenge for preference spaces beyond 8 dimensions, the proposed heuristics offer a powerful tool for data summarization. Future research may explore non-linear utility functions and more advanced geometric algorithms to further scale exact computation.

Summary updated

BibTeX
@inproceedings{storandt2019algorithms,
  author = {Sabine Storandt and Stefan Funke},
  title = {{Algorithms for Average Regret Minimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011600},
}
Figure