High-dimensional Regret Minimization

arXiv:2512.24078 · cs.DB, cs.CG, cs.IR · Submitted 2025-12-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "High-dimensional Regret Minimization".

Jane: Here's the gist of the paper. Multi-criteria decision making in large databases is very important in real world applications <ref:2512.24078#pg2> The FHDR framework is a novel approach that takes less than 0.01s with fewer than 30 rounds of interaction <ref:2512.24078#pg2> Extensive experiments demonstrate that FHDR outperforms the best-known algorithms by at least an order of magnitude in execution time and up to several orders of magnitude in terms of the number of interactions required <ref:2512.24078#pg2>.

Tom: Problem Context and Motivation Multi-criteria decision making in a large database containing a number of tuples/options is very important in real world applications <ref:2512.24078#pg2> The paper addresses the challenges of applying interactive regret minimization to high-dimensional datasets where existing algorithms either fail to scale or require excessive user interactions <ref:2512.24078#pg2>.

Jane: The authors are motivated by the observation that users rarely value all attributes equally, suggesting that the true utility vector is effectively sparse, with most weight concentrated on a small subset of attributes <ref:2512.24078#pg4> This sparsity assumption supports the framework's design <ref:2512.24078#pg4>.

Tom: Framework Structure and Phases The FHDR framework is organized into three phases to exploit the sparsity of the utility function <ref:2512.24078#pg5> 1.

Paper summary: Tom: So we're looking at this paper called "High-dimensional Regret Minimization," and the main idea is that we need a better way to make decisions when you have a massive database with hundreds of options and many attributes.

Jane: It tackles this by showing that existing interactive methods often fail when the number of attributes gets really high, or they just require way too many rounds of asking questions from the user.

Lu: The authors are motivated by a key observation: in practice, users don't value every single attribute equally; they usually focus on a much smaller subset of those attributes for their decision.

Meng: That sparsity assumption is what makes this framework interesting because it supports a design where we only spend effort on the important features.

Lalam: Exactly. The paper suggests that the true utility vector is effectively sparse, with most of the weight concentrated on a small group of attributes, which helps guide the system.

Tom: So, what's this FHDR framework they propose? They're trying to solve this problem by using three distinct phases to exploit that sparsity.

Jane: It starts with a coarse elimination phase where the system looks at all the attributes and tries to discard dimensions whose weight must be zero because they aren't useful.

Lu: Then, in the fine selection phase, it refines down to exactly those few key dimensions by using something called group testing and a generalized binary-splitting algorithm.

Meng: And finally, the third phase is just applying an adapted version of an existing interactive algorithm like UH-Random to find the best tuple with that reduced set of dimensions.

Lalam: It sounds like they are essentially reducing the problem space before running the main regret minimization step, which should make it much faster.

Tom: From what I'm seeing, they break down their dimension reduction into two parts: first, partitioning all those attributes into blocks and randomly selecting samples to eliminate irrelevant ones in batches.

Jane: And then the second part uses group testing on that smaller candidate set to identify the key dimensions using that binary-splitting algorithm to minimize how many queries are needed.

Lu: The theorem they present shows this two-phase design keeps the dimension reduction process efficient while keeping each question limited to a small number of attributes, say m attributes.

Meng: That sounds practical because it addresses both efficiency and usability concerns simultaneously, which is what I worry about when we ship models to production.

Lalam: And they claim this approach preserves an efficient dimension reduction process while ensuring a user-friendly interaction by keeping each question limited to m attributes, which is a big win for real-world use cases.

Tom: So how do the results compare? They tested FHDR against other methods like UtilityApprox and Sphere, and FHDR significantly cuts down the number of questions asked compared to those existing approaches.

Jane: And in a limited-feedback case, they showed that the regret ratio decreases steadily as more questions are answered, which proves its efficiency in reducing the output size with additional feedback.

Lu: Experiments on real datasets show that FHDR behaves exactly like synthetic ones, achieving a lower regret ratio than UtilityApprox and maintaining efficient runtime scaling approximately linearly with n.

Meng: That linear scaling is good because it means we can actually run this on larger datasets without waiting forever for computation time to explode.

Lalam: They confirm that FHDR maintains a stable regret ratio below zero point zero three on real data, which is significantly lower than UtilityApprox, showing the efficiency gains hold up in practice.

Tom: So what's the big picture here? The paper "High-dimensional Regret Minimization" introduces dimension reduction right into the interactive process itself to handle high dimensions effectively.

Jane: It bridges the gap between general applicability and practical constraints by creating efficient algorithms that can handle both complete and partial user feedback.

Lu: The framework develops algorithms that return either the optimal tuple or a compact representative set with a small regret ratio, even under limited feedback scenarios.

Meng: The authors note they are also looking at future work to incorporate noise-robust mechanisms or error-tolerant learning modules to handle inconsistent or unreliable user input.

Lalam: It seems the core idea is that by reducing the attribute space first, you can achieve a good result with far fewer interactions than what was previously possible.

Tom: The paper concludes that FHDR successfully addresses high-dimensional regret minimization by introducing this dimension reduction into the process itself to make it more practical.

Jane: It's about finding those small, important subsets of attributes that really matter to the user, which is a fundamental problem in multi-criteria decision making.

Lu: The implication is that for applications with hundreds of attributes, we can move from impractical interaction counts, like exceeding a thousand rounds in old methods, to something much more manageable.

Meng: If this works on real traffic at scale without huge computation time penalties, it’s definitely worth looking into deploying this kind of approach for complex user preferences.

Lalam: The method is robust under partial or limited feedback, returning either the optimal tuple with sufficient interaction or a compact representative set with a small regret ratio under limit feedback.

Conclusion: Tom: So, we've looked at how this FHDR framework works to handle huge databases with many choices and attributes. Now, let's wrap up what they actually did in the paper "High-dimensional Regret Minimization."

Jane: It seems like the whole point is that they figured out a way to make those high-dimensional problems practical for real applications, right? They focused on finding those important attributes without drowning in questions.

Lu: Yeah, they took this big problem—multi-criteria decision making in huge databases—and they introduced dimension reduction directly into the process of asking questions and getting feedback.

Meng: So, instead of just asking a million questions across all attributes, they first figure out which few attributes matter most before they even start minimizing regret. That's a big shift for deployment concerns.

Lalam: Exactly. The conclusion is that this framework successfully bridges the gap between having a theoretically sound method and actually being able to use it in the real world under practical constraints.

Tom: It really comes down to their authors figuring out how to use sparsity—the idea that users only care about a few things—to guide the entire decision-making process more efficiently.

Jane: And they show that this isn't just theory; they have experiments on real datasets where FHDR keeps its runtime efficient and its regret ratio low compared to other methods.

Lu: What’s interesting is how it handles both complete feedback, where the user answers everything, and partial feedback, where they only answer some questions along the way.

Meng: That flexibility with partial feedback is what I'm watching closely from a production standpoint because real users don't always finish answering all their questions.

Lalam: It means this method can return either the perfect choice or a very good representative set of choices, even when you only get limited input from the user.

Tom: It seems like they’ve built an algorithm that scales well and respects the limits of human interaction, which is something we need to think about when building more complex decision-making systems.

Jane: Before we look at how this specifically works in detail, we should talk about who wrote this and what kind of work they usually do.

Junyu Liao, Ashwin Lall, Mitsunori Ogihara, Raymond Chi-Wing Wong

The Hong Kong University of Science and Technology · Denison University · University of Miami

cs.DB, cs.CG, cs.IR

Submitted: 2025-12-30

Updated: 2026-11-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 88/100

The gist: Multi-criteria decision making in large databases is very important in real world applications <ref:2512.24078#pg2> The FHDR framework is a novel approach that takes less than 0.01s with fewer than…

Key concepts

Multi-criteria Decision Making
This is the process of choosing the best option from many choices based on several different criteria. In this paper, it deals with selecting a single 'best' tuple from a large database where users value different attributes unequally, meaning some attributes matter much more than others.
Sparsity Assumption
The core assumption is that user preferences are sparse; most attributes have little influence on the final choice. This allows the framework to focus its effort by first discarding irrelevant dimensions in Phase 1, significantly reducing the search space and improving efficiency.
FHDR Framework
This is a novel approach designed for high-dimensional regret minimization. It operates in three phases: coarse elimination of attributes, fine selection of key dimensions, and finally, regret minimization using an adapted interactive algorithm to find the maximum-utility tuple.

Terminology

Summary

Multi-criteria decision making in large databases is very important in real world applications <ref:2512. p. 0

Where the paper says it

edu Raymond Chi-Wing Wong The Hong Kong University of Science and Technology raywong@cse. hk Abstract Multi-criteria decision making in large databases is very important in real world applications.

24078#pg2> The FHDR framework is a novel approach that takes less than 0. p. 0
Where the paper says it

Existing interactive algorithms either fail to scale or require excessive user interactions (often exceeding 1000 rounds). Motivated by this, we propose FHDR (Fast High-Dimensional Reduction), a novel framework that takes less than 0.

01s with fewer than 30 rounds of interaction <ref:2512. p. 0
Where the paper says it

Motivated by this, we propose FHDR (Fast High-Dimensional Reduction), a novel framework that takes less than 0. 01𝑠 with fewer than 30 rounds of interaction.

24078#pg2> Extensive experiments demonstrate that FHDR outperforms the best-known algorithms by at least an order of magnitude in execution time and up to several orders of magnitude in terms of the number of interactions required <ref:2512. p. 0
Where the paper says it

It is considered a breakthrough in the field of interactive queries since most, if not all, existing studies are not scalable to high-dimensional datasets. Extensive experiments demonstrate that FHDR outperforms the best-known algorithms by at least an order of magnitude in execution time and up to several orders of magnitude in terms of the number of interactions required, establishing a new state of the art for scalable interactive regret minimization.

24078#pg2>.

Problem Context and Motivation

Multi-criteria decision making in a large database containing a number of tuples/options is very important in real world applications <ref:2512.24078#pg2> The paper addresses the challenges of applying interactive regret minimization to high-dimensional datasets where existing algorithms either fail to scale or require excessive user interactions <ref:2512. p. 0

Where the paper says it

Existing interactive algorithms either fail to scale or require excessive user interactions (often exceeding 1000 rounds). Motivated by this, we propose FHDR (Fast High-Dimensional Reduction), a novel framework that takes less than 0.

24078#pg2>. The authors are motivated by the observation that users rarely value all attributes equally, suggesting that the true utility vector is effectively sparse, with most weight concentrated on a small subset of attributes <ref:2512. p. 1
Where the paper says it

The success of “Take-The-Best” supports our assumption that the true utility vector is effectively sparse, with most weight concentrated on a small subset of attributes. The observation that users consider only a limited set of attributes is further supported by conjoint analysis [12, 40, 44, 46], a well-established method in marketing and psychology for quantifying how decision-makers trade off between features.

24078#pg4> This sparsity assumption supports the framework's design <ref:2512.24078#pg4>.

Framework Structure and Phases

The FHDR framework is organized into three phases to exploit the sparsity of the utility function <ref:2512.24078#pg5> 1. Phase 1, Coarse Elimination, begins with the full set of d attributes and repeatedly presents small batches of m dimensions drawn from the dataset to infer and discard dimensions whose associated weight must be zero <ref:2512. p. 4

Where the paper says it

We begin with the full set of 𝑑 attributes and repeatedly present the user with small batches of 𝑚 dimensions drawn from the dataset. By observing which tuples the user prefers, we infer and discard those dimensions whose associated weight must be zero.

24078#pg7>. 2. Phase 2, Fine Selection, refines down to exactly those dint key dimensions by group testing using a generalized binary-splitting algorithm <ref:2512. p. 4
Where the paper says it

Phase 2: Fine Selection. From the remaining attributes in the candidate pool, we refine down to exactly those 𝑑int key dimensions by group testing.

24078#pg7> 3. Phase 3, Regret Minimization, determines the maximum-utility-tuple with an adapted version of an existing interactive algorithm like UH-Random <ref:2512. p. 4
Where the paper says it

Phase 3: Regret Minimization. In this phase, we determine the maximum-utility-tuple, with an adapted version of existing interactive algorithm.

24078#pg7>.

Dimension Reduction Strategies

The dimension reduction process involves two phases to take advantage of the sparsity of the utility function <ref:2512.24078#pg7> 1. Phase 1 partitions the d attributes into blocks and randomly selects s tuples on each m-dimensional subspace, eliminating irrelevant attributes in batches <ref:2512. p. 5

Where the paper says it

Algorithm 1 Phase 2: Fine Selection via Group Testing Input: Candidate set Dcand of attributes (with |Dcand | ≤ 𝑑int𝑚), upper bound 𝑑max on 𝑑int Output: Updated set Dcand of size 𝑑int (larger if the user quits earlier) 1: 𝑑left ← 𝑑max, D′ cand ← ∅ /*𝑑left denotes the possible key attributes to be identified, and D′ cand contains the identified key attributes*/ 2: while 𝑑left > 0 and Dcand ≠ ∅ do 3: if user quits answering then break 4: if |Dcand | ≤ 2𝑑left − 2 then ⊲ Base case 5: for each dimension 𝐷𝑖 ∈ Dcand do 6: Construct dimension set D𝐷𝑖 = {𝐷𝑖 }∪ {random 𝑚 − 1 attributes identified as non-key in Phase 1} 7: Project dataset onto D𝐷𝑖 , show 𝑠 tuples to user 8: if user selects a tuple then 9: D′ cand ← D′ cand ∪ {𝑎}, 𝑑left ← 𝑑left − 1 10: Dcand ← Dcand \ {𝑎} 11: else ⊲ Group testing 12: 𝑙 ← |Dcand | − 𝑑left + 1, 𝛼 ← ⌊log2 (𝑙/𝑑left)⌋ 13: Randomly sample D ⊂ Dcand, |D | = 2 𝛼 14: Project dataset onto D, show 𝑠 tuples to user 15: if user selects a tuple then 16: Perform binary search on D to find one key attribute 𝑎 ∗ , at the same time identify 𝑥 attributes in D as non-key from user response 17: D′ cand ← D′ cand ∪ {𝑎 ∗ }, 𝑑left ← 𝑑left − 1 18: Dcand ← Dcand \ ({𝑎 ∗ } ∪ non-key attributes) 19: else 20: Dcand ← Dcand \ D 21: return Dcand ∪ D′ cand (3) If the user picks one tuple, all 𝑚 attributes in that block are potentially key, thus kept in Dcand; otherwise discard all the attributes in that block from the candidate set. By construction, any block containing tuples with non–zero weight will survive, while irrelevant blocks are eliminated in batches.

24078#pg7> 2. Phase 2 uses group testing to identify key dimensions from the candidate set Dcand, employing a generalized binary-splitting algorithm to minimize queries <ref:2512. p. 5
Where the paper says it

Algorithm 1 Phase 2: Fine Selection via Group Testing Input: Candidate set Dcand of attributes (with |Dcand | ≤ 𝑑int𝑚), upper bound 𝑑max on 𝑑int Output: Updated set Dcand of size 𝑑int (larger if the user quits earlier) 1: 𝑑left ← 𝑑max, D′ cand ← ∅ /*𝑑left denotes the possible key attributes to be identified, and D′ cand contains the identified key attributes*/ 2: while 𝑑left > 0 and Dcand ≠ ∅ do 3: if user quits answering then break 4: if |Dcand | ≤ 2𝑑left − 2 then ⊲ Base case 5: for each dimension 𝐷𝑖 ∈ Dcand do 6: Construct dimension set D𝐷𝑖 = {𝐷𝑖 }∪ {random 𝑚 − 1 attributes identified as non-key in Phase 1} 7: Project dataset onto D𝐷𝑖 , show 𝑠 tuples to user 8: if user selects a tuple then 9: D′ cand ← D′ cand ∪ {𝑎}, 𝑑left ← 𝑑left − 1 10: Dcand ← Dcand \ {𝑎} 11: else ⊲ Group testing 12: 𝑙 ← |Dcand | − 𝑑left + 1, 𝛼 ← ⌊log2 (𝑙/𝑑left)⌋ 13: Randomly sample D ⊂ Dcand, |D | = 2 𝛼 14: Project dataset onto D, show 𝑠 tuples to user 15: if user selects a tuple then 16: Perform binary search on D to find one key attribute 𝑎 ∗ , at the same time identify 𝑥 attributes in D as non-key from user response 17: D′ cand ← D′ cand ∪ {𝑎 ∗ }, 𝑑left ← 𝑑left − 1 18: Dcand ← Dcand \ ({𝑎 ∗ } ∪ non-key attributes) 19: else 20: Dcand ← Dcand \ D 21: return Dcand ∪ D′ cand (3) If the user picks one tuple, all 𝑚 attributes in that block are potentially key, thus kept in Dcand; otherwise discard all the attributes in that block from the candidate set. By construction, any block containing tuples with non–zero weight will survive, while irrelevant blocks are eliminated in batches.

24078#pg7> The theorem shows that this two-phase design preserves an efficient dimension reduction process while ensuring a user-friendly interaction by keeping each question limited to m attributes <ref:2512. p. 6
Where the paper says it

The size of the batch for the first group test in Phase 2 would be no more than 𝑚. By guaranteeing that every question involves only 𝑚 attributes, this two-phase design preserves an efficient dimension reduction process, while ensuring a user-friendly interaction.

24078#pg8>.

Performance and Results

The performance evaluation compares FHDR against UtilityApprox and Sphere, showing that FHDR significantly reduces the number of questions asked and achieves lower regret ratios compared to existing approaches <ref:2512.24078#pg10> In the limited-feedback case (Problem 2), the regret ratio decreases steadily as more questions are answered, demonstrating efficiency in reducing output size with additional feedback. p. 9

Where the paper says it

As a recap of the algorithm design, we will identify the user’s favorite tuple if Phase 2 is complete and the user proceeds the interaction, or otherwise use AttributeSubset to return a subset 𝑆 of tuples. Accordingly, the output size of our algorithm decreases rapidly with additional feedback, demonstrating efficiency.

Experiments on real datasets confirm that FHDR exhibits behavior consistent with synthetic datasets, achieving lower regret with fewer interactions and maintaining efficient runtime. p. 1
Where the paper says it

• We conducted extensive experiments on both synthetic and realworld datasets. Under consistent and well-justified settings, our proposed algorithm outperformed existing methods across several metrics including regret ratio, number of questions required, and execution time.

Usability and Practicality

The usability of the framework is addressed by allowing the user to skip or stop answering questions at any time, ensuring a user-friendly interaction process <ref:2512.24078#pg4> The user study results indicate that FHDR received significantly higher ratings than UtilityApprox, suggesting that its efficiency gains outweigh minor potential losses in accuracy. p. 2

Where the paper says it

Importantly, the number of required interactions is significantly reduced compared to existing interactive approaches, thereby lowering user effort without sacrificing accuracy. By effectively scaling regret minimization to higher dimensions, our framework enables practical and accurate decision support in complex, real-world scenarios involving multiple criteria.

The choice of parameters, such as setting m=7, balances query efficiency with cognitive limits suggested by cognitive science literature <ref:2512.24078#pg4>.

Conclusion and Future Work

The paper concludes that FHDR successfully bridges the gap between general applicability and practical constraints in high-dimensional regret minimization by introducing dimension reduction into the process The framework develops efficient algorithms that handle both complete and partial user feedback, returning either the optimal tuple or a compact representative set with a small regret ratio. Future work is suggested to incorporate noise-robust mechanisms or error-tolerant learning modules to make the framework more resilient to inconsistent or unreliable user input.

Algorithm Summary

The overall algorithm consists of a three-phase framework tailored for high-dimensional k-regret minimization under sparse user preferences <ref:2512.24078#pg9> Phase 1 progressively reduces the attribute space through coarse elimination and Phase 2 refines down to exactly those dint key dimensions <ref:2512. p. 7

Where the paper says it

4 Summary Our algorithm consists of a three-phase framework tailored for high-dimensional 𝑘-regret minimization under sparse user preferences. The first two phases progressively reduce the attribute space through coarse elimination and fine selection, identifying a small set of candidate dimensions with minimal user effort.

24078#pg9>. The third phase applies an adapted interactive method UH-Random to locate the user’s favorite tuple <ref:2512. p. 7
Where the paper says it

The first two phases progressively reduce the attribute space through coarse elimination and fine selection, identifying a small set of candidate dimensions with minimal user effort. The third phase applies an adapted interactive method UH-Random to locate the user’s favorite tuple.

24078#pg9> In the single-round AttributeSubset algorithm, the process involves randomly sampling distinct attributes from Dcand and running Sphere on a lower-dimensional subspace to obtain a regret-minimizing set. p. 7
Where the paper says it

Within each, we randomly sample 𝑤 distinct attributes from the candidate set Dcand. We then select out the skyline points and run Sphere on the lower-dimensional subspace (i.

The confidence level for the number of rounds needed is given by N = ln(1−Pcover) / ln(1−Pcover), where Pcover is the probability that all dint attributes are covered in the random sample. p. 8
Where the paper says it

High-dimensional Regret Minimization level with respect to the number of rounds, or the number of rounds needed for a certain confidence level. Denote the probability that all 𝑑int attributes are covered in the random sample of size 𝑤 as 𝑃cover.

Experimental Findings

Experiments on synthetic and real datasets demonstrate that FHDR achieves lower regret with fewer interactions and maintaining efficient runtime compared to existing approaches In Problem 1, the number of questions required by FHDR increases moderately as dint grows, while UtilityApprox requires a much larger number of questions. In Problem 2, the regret ratio decreases steadily as more questions are answered, eventually approaching zero when Phase 2 completes. p. 9

Where the paper says it

This assumption is also reasonable in high-dimensional contexts, where users are typically more willing to provide slightly more feedback. As shown in Figure 6, the regret ratio decreases steadily as more questions are answered, eventually approaching zero when Phase 2 completes.

The performance analysis on real datasets shows that FHDR maintains a stable regret ratio below 0. p. 9
Where the paper says it

Figures 9 and 10 present the scalability results with respect to the number of tuples 𝑛 and dimensionality 𝑑. When varying 𝑛, our algorithm maintains a stable regret ratio below 0.

03, significantly lower than UtilityApprox, and its execution time scales approximately linearly with n. p. 9
Where the paper says it

03, significantly lower than that of UtilityApprox, whose regret increases noticeably. The execution time of our method scales approximately linearly with 𝑛, while Sphere-Adapt, consistent with its complexity 𝑂(𝑛𝑒𝑂 ( √ 𝑑 log𝑛) + 𝑛𝑘3𝑑) [50], grows faster than sub-exponentially.

Key Takeaways

The key takeaways are that the framework effectively identifies a small set of attributes that best represent user preferences <ref:2512.24078#pg4> The method is robust under partial or limited feedback, returning either the optimal tuple with sufficient interaction or a compact representative set with a small regret ratio under limit feedback The sampling strategy in AttributeSubset is able to preserve representative tuples in the original space while significantly reducing execution time. The chosen parameter w=6 is selected because it achieves both efficiency and accuracy. p. 7

Where the paper says it

Sphere assumes utility functions depend on all 𝑑 attributes, whereas in practice, users consider only a small subset (𝑑int ≪ 𝑑). Ignoring this sparsity limits accuracy and efficiency.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved Interactive Query Efficiency for High-Dimensional Data: The proposed FHDR framework can take less than 0.01s with fewer than 30 rounds of interaction, representing a breakthrough since most, if not all, existing studies are not scalable to high-dimensional datasets.

  2. Enhanced User Preference Modeling: The system can effectively learn the user's implicit utility function by iteratively refining recommendations based on user choices, moving beyond the limitations of single-round queries which naturally raises the question: can multiple rounds of interaction further reduce regret or output size?

  3. Scalable Attribute Identification for Sparse Utility Vectors: The two-phase dimension reduction (Phase 1 and Phase 2) allows the algorithm to identify a small set of key attributes with minimal user effort, exploiting the assumption that the true utility vector u is effectively sparse, with most weight concentrated on a small subset of attributes.

  4. Robust Handling of Partial Feedback: The system can return a low regret ratio even when users provide limited feedback by using the AttributeSubset algorithm to select a subset of tuples, as this approach bridges the gap between the general applicability of Sphere and the practical constraints while demonstrating that our method consistently achieves a regret ratio more than five times lower than UtilityApprox.

  5. Adaptive Output Size Selection: The system can dynamically return either the user's favorite tuple or a compact representative set with a small regret ratio, ensuring that the returned set is not useful without high quality, the method cannot scale without efficiency, and the approach is unlikely to be adopted in practice without usability.

Abstract

Multi-criteria decision making over large databases is fundamental to many real-world applications. Interactive regret minimization has emerged recently as a promising approach that combines the controllable output size of top- k queries with the flexibility of skyline queries, without requiring users to explicitly specify a utility function. Instead, the system iteratively presents a small set of options, learns the user's implicit preferences from their selections, and progressively refines its recommendations. However, modern applications such as housing search and financial product selection often involve hundreds of attributes. Existing interactive methods either fail to scale to such high-dimensional data or require excessive user interaction, frequently exceeding 1000 rounds. We address this limitation with FHDR (Fast High-Dimensional Reduction), a framework that exploits sparse linear preferences to discover key attributes through lightweight interactions. We also propose AttributeSubset, an efficient single-round algorithm that returns a compact recommendation set without further feedback. In our experiments on real datasets, FHDR completes in under 0.03 s and requires fewer than 30 interaction rounds under the default setting. Extensive experiments on both synthetic and real-world datasets show that FHDR outperforms the best-known baselines by at least one order of magnitude in execution time and by up to several orders of magnitude in interaction cost. These results establish FHDR as a new state of the art for scalable interactive regret minimization.

Sources

Related papers