Probably Approximately Consensus: On the Learning Theory of Finding Common Ground

• URL: http://arxiv.org/abs/2604.21811v1
• Date: Thu, 23 Apr 2026 16:06:41 GMT
• Title: Probably Approximately Consensus: On the Learning Theory of Finding Common Ground
• Abstract summary: We model consensus as an interval in a one-dimensional opinion space derived from potentially high-dimensional data.<n>We propose an efficient Empirical Risk Minimization (ERM) algorithm and establish PAC-learning guarantees.
• Score: 14.350399184122502
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A primary goal of online deliberation platforms is to identify ideas that are broadly agreeable to a community of users through their expressed preferences. Yet, consensus elicitation should ideally extend beyond the specific statements provided by users and should incorporate the relative salience of particular topics. We address this issue by modelling consensus as an interval in a one-dimensional opinion space derived from potentially high-dimensional data via embedding and dimensionality reduction. We define an objective that maximizes expected agreement within a hypothesis interval where the expectation is over an underlying distribution of issues, implicitly taking into account their salience. We propose an efficient Empirical Risk Minimization (ERM) algorithm and establish PAC-learning guarantees. Our initial experiments demonstrate the performance of our algorithm and examine more efficient approaches to identifying optimal consensus regions. We find that through selectively querying users on an existing sample of statements, we can reduce the number of queries needed to a practical number.

Related papers

• Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback [59.287761696290865]
  We propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback.<n>We demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.
  arXiv  Detail & Related papers  (2026-02-09T06:29:54Z)
• Wild Guesses and Mild Guesses in Active Concept Learning [0.0]
  We study a trade-off in a neuro-symbolic Bayesian learner whose hypotheses are proposed by a large language model (LLM)<n>We compare a Rational Active Learner that selects queries to maximize approximate expected information gain (EIG) and the human-like Positive Test Strategy (PTS)<n>Our results suggest that "confirmation bias" may not be a cognitive error, but rather a rational adaptation for maintaining tractable inference in the sparse, open-ended hypothesis spaces characteristic of human thought.
  arXiv  Detail & Related papers  (2026-02-06T16:04:44Z)
• A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes [4.299934797034146]
  We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses.<n>We propose a novel learning paradigm that relies on stronger incorporation of empirical data and less algorithmic decisions to be based on prior assumptions.
  arXiv  Detail & Related papers  (2025-11-13T06:02:55Z)
• Conformal Information Pursuit for Interactively Guiding Large Language Models [68.16703423481935]
  This paper explores sequential querying strategies that aim to minimize the expected number of queries.<n>One such strategy is Information Pursuit (IP), a greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty.<n>We propose Conformal Information Pursuit (C-IP), an alternative approach to sequential information gain based on conformal prediction sets.
  arXiv  Detail & Related papers  (2025-07-04T03:55:39Z)
• Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time [52.230936493691985]
  We propose SITAlign, an inference framework that addresses the multifaceted nature of alignment by maximizing a primary objective while satisfying threshold-based constraints on secondary criteria.<n>We provide theoretical insights by deriving sub-optimality bounds of our satisficing based inference alignment approach.
  arXiv  Detail & Related papers  (2025-05-29T17:56:05Z)
• Individualised Counterfactual Examples Using Conformal Prediction Intervals [12.895240620484572]
  High-dimensional feature spaces that are typical of machine learning classification models admit many possible counterfactual examples to a decision.<n>We explicitly model the knowledge of the individual, and assess the uncertainty of predictions which the individual makes by the width of a conformal prediction interval.<n>We present a synthetic data set on a hypercube which allows us to fully visualise the decision boundary.<n>Second, in this synthetic data set we explore the impact of a single CPICF on the knowledge of an individual locally around the original query.
  arXiv  Detail & Related papers  (2025-05-28T13:13:52Z)
• Prediction-Powered E-Values [0.66567375919026]
  We apply ideas of prediction-powered inference to e-values.<n>We show that every inference procedure that can be framed in terms of e-values has a prediction-powered counterpart.<n>Our approach is modular and easily integrable into existing algorithms.
  arXiv  Detail & Related papers  (2025-02-06T18:36:01Z)
• Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm [14.980926991441345]
  We show that datasets containing interventional data can be effectively extracted under realistic assumptions about the data distribution.<n>We introduce a novel variant of interventional faithfulness, which relies on comparisons between the marginal distributions of each variable across observational and interventional settings.<n>We also introduce Intersort, an algorithm designed to infer the causal order from datasets containing large numbers of single-variable interventions.
  arXiv  Detail & Related papers  (2024-05-28T16:07:17Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  Multi-distribution learning seeks to learn a shared model that minimizes the worst-case risk across $k$ distinct data distributions.<n>We propose a novel algorithm that yields an varepsilon-optimal randomized hypothesis with a sample complexity on the order of (d+k)/varepsilon2.
  arXiv  Detail & Related papers  (2023-12-08T16:06:29Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• The Minority Matters: A Diversity-Promoting Collaborative Metric Learning Algorithm [154.47590401735323]
  Collaborative Metric Learning (CML) has recently emerged as a popular method in recommendation systems. This paper focuses on a challenging scenario where a user has multiple categories of interests. We propose a novel method called textitDiversity-Promoting Collaborative Metric Learning (DPCML)
  arXiv  Detail & Related papers  (2022-09-30T08:02:18Z)
• Beyond Individualized Recourse: Interpretable and Interactive Summaries of Actionable Recourses [14.626432428431594]
  We propose a novel model framework called Actionable Recourse agnostic (AReS) to construct global counterfactual explanations. We formulate a novel objective which simultaneously optimize for correctness of the recourses and interpretability of the explanations. Our framework can provide decision makers with a comprehensive overview of recourses corresponding to any black box model.
  arXiv  Detail & Related papers  (2020-09-15T15:14:08Z)

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.