Research map / Learning theory and algorithms / Sample complexity
Forecasting Competitions with Correlated Events
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.
Extends Multiplicative Weights forecasting competitions to correlated events via a new (b,c)-block correlation notion, proving approximate truthfulness and an O(b^2 log(n)/eps^2) event-complexity accuracy guarantee with a novel concentration bound.
Problem
Forecasting competition mechanisms are typically analyzed assuming independent events, yet real forecasting events are correlated; the paper asks which correlation structures allow accurate, approximately truthful forecaster selection.
Approach
Introduces (b,c)-block correlation, where each event is strongly influenced by at most b others and weakly (within c) by the rest, and shows Multiplicative Weights mechanism remains approximately truthful and accurate under it, using a new concentration bound built from a pair of connected martingales.
Key results
- Under (b,c)-block correlation with c=O(eps), Multiplicative Weights selects an eps-optimal forecaster w.p. 1-delta using m=O(b^2 log(n)/eps^2) events (Theorem 2, m* = 400b^2 ln(8n/delta)/eps^2).
- Multiplicative Weights is gamma-approximately truthful with gamma=(3b+1)eta+c for eta<1/(3b) under block correlation (Theorem 1).
- A new concentration bound (Theorem 3) for block-correlated [0,1] variables gives deviations of mc + 2b sqrt(2m ln(4/delta)) with probability at least 1-delta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Multiplicative Weights with η = ϵ/(80b) for (b, ϵ/20)-block-correlated events | forecasting competition · (b, ϵ/20)-block-correlated events | event complexity: m ≥ m* = 400b² ln(8n/δ)/ϵ² | Helped |
| Allow events to have (b, c)-block correlation rather than requiring independence | Multiplicative Weights · forecasting competitions | event complexity: O(b² log(n)/ϵ²); O(log(n)/ϵ²) | Mixed |
| Use Multiplicative Weights with (b, c)-block-correlated beliefs | forecasting competition · (b, c)-block-correlated beliefs | approximate truthfulness bound: γ = (3b + 1)η + c | Helped |
Surprising findings
- Entropy and covariance-based correlation measures are not tractable for forecaster selection: a random-bias model can have arbitrarily high entropy while a perfect forecaster may never win w.h.p.
Limitations
- Accuracy analysis only proven for Multiplicative Weights; approximate truthfulness extended to FTRL but efficiency not shown for other regularizers.
- Block correlation is sufficient but not known to be necessary.
- All forecasters are assumed to share the same (b,c)-block correlation constants in their beliefs.
Experimental setup
Metrics: epsilon-optimal forecaster selection probability approximate truthfulness gamma event complexity
Baselines: Event Lotteries Forecasting (ELF) winner-take-all mechanism
Builds on: Multiplicative Weights forecasting mechanism (Frongillo et al. 2021) Event Lotteries Forecasting (Witkowski et al. 2023) Azuma-Hoeffding inequality
Closest papers by meaning
- Hedging and Approximate Truthfulness in Traditional Forecasting Competitions (AAAI 2025 · similarity 0.87)
- Conditional Forecasts and Proper Scoring Rules for Reliable and Accurate Performative Predictions (NeurIPS 2025 · similarity 0.82)
- Homogeneous Algorithms Can Reduce Competition in Personalized Pricing (NeurIPS 2025 · similarity 0.82)
- Online Learning in Betting Markets: Profit versus Prediction (ICML 2024 · similarity 0.82)
- Online Prediction with Limited Selectivity (NeurIPS 2025 · similarity 0.81)
- Winner-takes-all for Multivariate Probabilistic Time Series Forecasting (ICML 2025 · similarity 0.81)
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.