# High-Dimensional Prediction for Sequential Decision Making

arXiv: https://arxiv.org/abs/2310.17651 · HTML: https://mlsanity.com/paper/2310.17651/

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 92 references that are in the map.
- First posted on arXiv 26 Oct 2023.

## Builds on (most cited first, 30 of 30)

- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Conformal Prediction With Conditional Guarantees](https://mlsanity.com/paper/2305.12616/) (2023)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Batch Multivalid Conformal Prediction](https://mlsanity.com/paper/2209.15145/) (2022)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Flexible distribution-free conditional predictive bands using density estimators](https://mlsanity.com/paper/1910.05575/) (2019)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Generalization Bounds in the Predict-then-Optimize Framework](https://mlsanity.com/paper/1905.11488/) (2019)
- [Improving Conditional Coverage via Orthogonal Quantile Regression](https://mlsanity.com/paper/2106.00394/) (2021)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [Multicalibration as Boosting for Regression](https://mlsanity.com/paper/2301.13767/) (2023)
- [Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration](https://mlsanity.com/paper/2302.06726/) (2023)
- [A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning](https://mlsanity.com/paper/2302.10863/) (2023)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [HappyMap: A Generalized Multi-calibration Method](https://mlsanity.com/paper/2303.04379/) (2023)
- ["Calibeating": Beating Forecasters at Their Own Game](https://mlsanity.com/paper/2209.04892/) (2022)
- [Knowing what you know: valid and validated confidence sets in multiclass and multilabel prediction](https://mlsanity.com/paper/2004.10181/) (2020)
- [Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games](https://mlsanity.com/paper/2307.05448/) (2023)
- [Oracle Efficient Algorithms for Groupwise Regret](https://mlsanity.com/paper/2310.04652/) (2023)

## Built on by (most cited first, 30 of 41)

- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [Decision Theoretic Foundations for Conformal Prediction: Optimal Uncertainty Quantification for Risk-Averse Agents](https://mlsanity.com/paper/2502.02561/) (2025)
- [Length Optimization in Conformal Prediction](https://mlsanity.com/paper/2406.18814/) (2024)
- [Self-Calibrating Conformal Prediction](https://mlsanity.com/paper/2402.07307/) (2024)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [The Relative Value of Prediction in Algorithmic Decision Making](https://mlsanity.com/paper/2312.08511/) (2023)
- [Fair Risk Control: A Generalized Framework for Calibrating Multi-group Fairness Risks](https://mlsanity.com/paper/2405.02225/) (2024)
- [From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs](https://mlsanity.com/paper/2411.17582/) (2024)
- [The Relationship between No-Regret Learning and Online Conformal Prediction](https://mlsanity.com/paper/2502.10947/) (2025)
- [High dimensional online calibration in polynomial time](https://mlsanity.com/paper/2504.09096/) (2025)
- [High-Dimensional Calibration from Swap Regret](https://mlsanity.com/paper/2505.21460/) (2025)
- [Can a calibration metric be both testable and actionable?](https://mlsanity.com/paper/2502.19851/) (2025)
- [Networked Information Aggregation via Machine Learning](https://mlsanity.com/paper/2507.09683/) (2025)
- [Algorithms with Calibrated Machine Learning Predictions](https://mlsanity.com/paper/2502.02861/) (2025)
- [Orthogonal Causal Calibration](https://mlsanity.com/paper/2406.01933/) (2024)
- [In Defense of Defensive Forecasting](https://mlsanity.com/paper/2506.11848/) (2025)
- [Sample-Efficient Omniprediction for Proper Losses](https://mlsanity.com/paper/2510.12769/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Optimal Decision-Making Based on Prediction Sets](https://mlsanity.com/paper/2602.00989/) (2026)
- [The Benefit of Being Bayesian in Online Conformal Prediction](https://mlsanity.com/paper/2410.02561/) (2024)
- [Sparsity-Based Interpolation of External, Internal and Swap Regret](https://mlsanity.com/paper/2502.04543/) (2025)
- [Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration](https://mlsanity.com/paper/2503.18025/) (2025)
- [Robust Decision Making with Partially Calibrated Forecasts](https://mlsanity.com/paper/2510.23471/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Dimension-Free Decision Calibration for Nonlinear Loss Functions](https://mlsanity.com/paper/2504.15615/) (2025)
- [Calibrated Multi-Level Quantile Forecasting](https://mlsanity.com/paper/2512.23671/) (2025)
- [Near-optimal Swap Regret Minimization for Convex Losses](https://mlsanity.com/paper/2602.08862/) (2026)

## Abstract (arXiv)

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 L2 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.