Tractable Agreement Protocols

• URL: http://arxiv.org/abs/2411.19791v1
• Date: Fri, 29 Nov 2024 15:52:59 GMT
• Title: Tractable Agreement Protocols
• Authors: Natalie Collina, Surbhi Goel, Varun Gupta, Aaron Roth,
• Abstract summary: We present an efficient reduction that converts any machine learning algorithm into an interactive protocol. In our protocol, the model first provides a prediction, the human then responds by either agreeing or offering feedback. Our protocols rely on simple, efficient conditions and produce predictions that surpass the accuracy of any individual party's alone.
• Score: 17.313852884203314
• License:
• Abstract: We present an efficient reduction that converts any machine learning algorithm into an interactive protocol, enabling collaboration with another party (e.g., a human) to achieve consensus on predictions and improve accuracy. This approach imposes calibration conditions on each party, which are computationally and statistically tractable relaxations of Bayesian rationality. These conditions are sensible even in prior-free settings, representing a significant generalization of Aumann's classic "agreement theorem." In our protocol, the model first provides a prediction. The human then responds by either agreeing or offering feedback. The model updates its state and revises its prediction, while the human may adjust their beliefs. This iterative process continues until the two parties reach agreement. Initially, we study a setting that extends Aumann's Agreement Theorem, where parties aim to agree on a one-dimensional expectation by iteratively sharing their current estimates. Here, we recover the convergence theorem of Aaronson'05 under weaker assumptions. We then address the case where parties hold beliefs over distributions with d outcomes, exploring two feedback mechanisms. The first involves vector-valued estimates of predictions, while the second adopts a decision-theoretic approach: the human, needing to take an action from a finite set based on utility, communicates their utility-maximizing action at each round. In this setup, the number of rounds until agreement remains independent of d. Finally, we generalize to scenarios with more than two parties, where computational complexity scales linearly with the number of participants. Our protocols rely on simple, efficient conditions and produce predictions that surpass the accuracy of any individual party's alone.

Related papers

• Reconciling Model Multiplicity for Downstream Decision Making [24.335927243672952]
  We show that even when the two predictive models approximately agree on their individual predictions almost everywhere, it is still possible for their induced best-response actions to differ on a substantial portion of the population. We propose a framework that calibrates the predictive models with regard to both the downstream decision-making problem and the individual probability prediction.
  arXiv  Detail & Related papers  (2024-05-30T03:36:46Z)
• Best Practices for 2-Body Pose Forecasting [58.661899246497896]
  We review the progress in human pose forecasting and provide an in-depth assessment of the single-person practices that perform best. Other single-person practices do not transfer to 2-body, so the proposed best ones do not include hierarchical body modeling or attention-based interaction encoding. Our proposed 2-body pose forecasting best practices yield a performance improvement of 21.9% over the state-of-the-art on the most recent ExPI dataset.
  arXiv  Detail & Related papers  (2023-04-12T10:46:23Z)
• DeFeeNet: Consecutive 3D Human Motion Prediction with Deviation Feedback [23.687223152464988]
  We propose DeFeeNet, a simple yet effective network that can be added on existing one-off prediction models. We show that our proposed network improves consecutive human motion prediction performance regardless of the basic model.
  arXiv  Detail & Related papers  (2023-04-10T10:18:23Z)
• What Should I Know? Using Meta-gradient Descent for Predictive Feature Discovery in a Single Stream of Experience [63.75363908696257]
  computational reinforcement learning seeks to construct an agent's perception of the world through predictions of future sensations. An open challenge in this line of work is determining from the infinitely many predictions that the agent could possibly make which predictions might best support decision-making. We introduce a meta-gradient descent process by which an agent learns what predictions to make, 2) the estimates for its chosen predictions, and 3) how to use those estimates to generate policies that maximize future reward.
  arXiv  Detail & Related papers  (2022-06-13T21:31:06Z)
• A Confidence Machine for Sparse High-Order Interaction Model [16.780058676633914]
  Conformal prediction (CP) is a promising approach for obtaining the confidence of prediction results with fewer theoretical assumptions. We develop a full-CP of sparse high-order interaction model (SHIM) which is sufficiently flexible as it can take into account high-order interactions among variables.
  arXiv  Detail & Related papers  (2022-05-28T03:23:56Z)
• Test-time Collective Prediction [73.74982509510961]
  Multiple parties in machine learning want to jointly make predictions on future test points. Agents wish to benefit from the collective expertise of the full set of agents, but may not be willing to release their data or model parameters. We explore a decentralized mechanism to make collective predictions at test time, leveraging each agent's pre-trained model.
  arXiv  Detail & Related papers  (2021-06-22T18:29:58Z)
• Universal Off-Policy Evaluation [64.02853483874334]
  We take the first steps towards a universal off-policy estimator (UnO) We use UnO for estimating and simultaneously bounding the mean, variance, quantiles/median, inter-quantile range, CVaR, and the entire cumulative distribution of returns.
  arXiv  Detail & Related papers  (2021-04-26T18:54:31Z)
• Private Prediction Sets [72.75711776601973]
  Machine learning systems need reliable uncertainty quantification and protection of individuals' privacy. We present a framework that treats these two desiderata jointly. We evaluate the method on large-scale computer vision datasets.
  arXiv  Detail & Related papers  (2021-02-11T18:59:11Z)
• Double Robust Representation Learning for Counterfactual Prediction [68.78210173955001]
  We propose a novel scalable method to learn double-robust representations for counterfactual predictions. We make robust and efficient counterfactual predictions for both individual and average treatment effects. The algorithm shows competitive performance with the state-of-the-art on real world and synthetic data.
  arXiv  Detail & Related papers  (2020-10-15T16:39:26Z)

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.