High-Dimensional Prediction for Sequential Decision Making

• URL: http://arxiv.org/abs/2310.17651v2
• Date: Fri, 27 Oct 2023 17:59:29 GMT
• Title: High-Dimensional Prediction for Sequential Decision Making
• Authors: Georgy Noarov, Ramya Ramalingam, Aaron Roth, Stephan Xie
• Abstract summary: We study the problem of making predictions of an adversarially chosen high-dimensional state that are unbiased subject to an arbitrary collection of conditioning events. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing an appropriate set of conditioning events.
• Score: 9.684829814477526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of making predictions of an adversarially chosen high-dimensional state that are unbiased subject to an arbitrary collection of conditioning events, with the goal of tailoring these events to downstream decision makers. We give efficient algorithms for solving this problem, as well as a number of applications that stem from choosing an appropriate set of conditioning events. For example, we can efficiently make predictions targeted at polynomially many decision makers, giving each of them optimal swap regret if they best-respond to our predictions. We generalize this to online combinatorial optimization, where the decision makers have a very large action space, to give the first algorithms offering polynomially many decision makers no regret on polynomially many subsequences that may depend on their actions and the context. We apply these results to get efficient no-subsequence-regret algorithms in extensive-form games (EFGs), yielding a new family of regret guarantees for EFGs that generalizes some existing EFG regret notions, e.g. regret to informed causal deviations, and is generally incomparable to other known such notions. Next, we develop a novel transparent alternative to conformal prediction for building valid online adversarial multiclass prediction sets. We produce class scores that downstream algorithms can use for producing valid-coverage prediction sets, as if these scores were the true conditional class probabilities. We show this implies strong conditional validity guarantees including set-size-conditional and multigroup-fair coverage for polynomially many downstream prediction sets. Moreover, our class scores can be guaranteed to have improved $L_2$ loss, cross-entropy loss, and generally any Bregman loss, compared to any collection of benchmark models, yielding a high-dimensional real-valued version of omniprediction.

Related papers

• Optimal Transport-based Conformal Prediction [8.302146576157497]
  Conformal Prediction (CP) is a principled framework for uncertainty in blackbox learning models. We introduce a novel CP procedure handling prediction score functions through a lens. We then adapt our method for quantifying multi-output regression and multiclass classification.
  arXiv  Detail & Related papers  (2025-01-31T09:48:28Z)
• Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
  Generative models lack rigorous statistical guarantees for their outputs. We propose a sequential conformal prediction method producing prediction sets that satisfy a rigorous statistical guarantee. This guarantee states that with high probability, the prediction sets contain at least one admissible (or valid) example.
  arXiv  Detail & Related papers  (2024-10-02T15:26:52Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  Cascades are a classical strategy to enable inference cost to vary adaptively across samples. A deferral rule determines whether to invoke the next classifier in the sequence, or to terminate prediction. Despite being oblivious to the structure of the cascade, confidence-based deferral often works remarkably well in practice.
  arXiv  Detail & Related papers  (2023-07-06T04:13:57Z)
• Bayesian Optimization with Conformal Prediction Sets [44.565812181545645]
  Conformal prediction is an uncertainty quantification method with coverage guarantees even for misspecified models. We propose conformal Bayesian optimization, which directs queries towards regions of search space where the model predictions have guaranteed validity. In many cases we find that query coverage can be significantly improved without harming sample-efficiency.
  arXiv  Detail & Related papers  (2022-10-22T17:01:05Z)
• Generalizing Bayesian Optimization with Decision-theoretic Entropies [102.82152945324381]
  We consider a generalization of Shannon entropy from work in statistical decision theory. We first show that special cases of this entropy lead to popular acquisition functions used in BO procedures. We then show how alternative choices for the loss yield a flexible family of acquisition functions.
  arXiv  Detail & Related papers  (2022-10-04T04:43:58Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  We propose a generalization of conformal prediction to multiple learnable parameters. We show that it achieves approximate valid population coverage and near-optimal efficiency within class. Experiments show that our algorithm is able to learn valid prediction sets and improve the efficiency significantly.
  arXiv  Detail & Related papers  (2022-02-22T18:37:23Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• The Perils of Learning Before Optimizing [16.97597806975415]
  We show how prediction models can be learned end-to-end by differentiating through the optimization task. We show that the performance gap between a two-stage and end-to-end approach is closely related to the emphprice of correlation concept in optimization.
  arXiv  Detail & Related papers  (2021-06-18T20:43:47Z)
• Efficient Conformal Prediction via Cascaded Inference with Expanded Admission [43.596058175459746]
  We present a novel approach for conformal prediction (CP) We aim to identify a set of promising prediction candidates -- in place of a single prediction. This set is guaranteed to contain a correct answer with high probability.
  arXiv  Detail & Related papers  (2020-07-06T23:13:07Z)

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.