Research map / Bandits and online learning / Online convex optimization and games
High-Dimensional Prediction for Sequential Decision Making
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives efficient online algorithms for high-dimensional predictions that are unbiased conditional on polynomially many (context- and prediction-dependent) events, with applications to subsequence regret, extensive-form games, and transparent-coverage prediction sets.
Problem
Making adversarially-chosen high-dimensional predictions that are unbiased conditional on many events, which is computationally and statistically hard for calibration in high dimensions, and making these predictions useful to downstream decision makers and uncertainty quantification.
Approach
Reduces event-conditional unbiasedness to a minimax game over per-event experts (using MsMwC for adaptive regret), then solves the game efficiently: via the ellipsoid method for disjoint binary events and via follow-the-perturbed-leader otherwise, with bias scaling as sqrt of event frequency and log of dimension and event count.
Key results
- Unbiased predictions with bias O(ln(d|E|T) + sqrt(ln(d|E|T) * sum E[E^2])) for any event collection, per Theorem 1.
- Per-round running time polylogarithmic in t for disjoint binary events via the ellipsoid method; polynomial in t in the general case.
- Yields diminishing subsequence regret for any polynomial number of decision makers and subsequences, including the first efficient large-action-space results for online combinatorial optimization.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UnbiasedPrediction for predictions conditioned on a collection of events | Online adversarial high-dimensional prediction · Arbitrary event collection | event-conditional bias: O\left(\ln(2d|\mathcal{E}|T)+\sqrt{\ln(2d|\mathcal{E}|T) \sum_{t=1}^T \E_{p_t \sim \psi_t}[(E(x_t,p_t))^2]}\right) | Helped |
Limitations
- General-case running time is polynomial in 1/epsilon rather than logarithmic, and FTPL requires sampling or oracle assumptions.
- Results are theoretical; no empirical evaluation is reported in the provided text.
Experimental setup
Metrics: bias bound swap regret subsequence regret Brier score
Baselines: conformal prediction multicalibration swap regret algorithms decision calibration
Builds on: multiscale multiplicative weights with correction follow the perturbed leader Blackwell approachability decision calibration omniprediction
Closest papers by meaning
- Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning (NeurIPS 2016 · similarity 0.89)
- Stochastic and Adversarial Online Learning without Hyperparameters (NeurIPS 2017 · similarity 0.88)
- High-Dimensional Calibration from Swap Regret (NeurIPS 2025 · similarity 0.88)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.87)
- Near-Optimal Regret in Adversarial Kernel Bandits (NeurIPS 2026 · similarity 0.87)
- No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need! (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.