Research map / Learning theory and algorithms / Prediction and decision losses
Online Prediction with Limited Selectivity
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.
Introduces Prediction with Limited Selectivity, where a forecaster may only predict at a subset of timesteps, and gives instance-dependent upper/lower error bounds via an "approximate uniformity" measure plus average-case tightness for random stopping-time sets.
Problem
Selective mean prediction assumes the forecaster can predict at any time; the paper asks how well one can forecast the average of unseen numbers when predictions are only allowed at a prescribed subset of timesteps.
Approach
Generalizes selective prediction to a stopping-time set T and characterizes optimal worst-case error via a combinatorial complexity measure (approximate uniformity of block lengths), with an algorithm achieving O(1/log U) and matching lower bounds on average for random T.
Key results
- Upper bound O(1/log U~(L)) on worst-case error for every PLS instance, generalizing Drucker's O(1/log n).
- Lower bounds Omega(max{1/U~^2, 1/log m}) on worst-case error for every instance with m blocks.
- For p*-random stopping times with k-monotone p*, upper and lower bounds match up to constant factor with high probability when sum of p* is at least polylog(n) (k=O(1)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an approximately uniform-block forecasting algorithm when the block-length ratio is at most C | PLS with m blocks · PLS instances with block-length ratio at most C | worst-case squared error: O(C/ \log m) | Helped |
| Use approximate uniformity to construct the forecasting algorithm | PLS instance L · PLS instance L | worst-case squared error: O(1/\log\widetilde{U}(\mathcal{L})) | Helped |
| Increase the number of blocks to m | Any PLS instance · PLS with m blocks | worst-case squared error: \Omega(1 / \log m) | Hurt |
| Use a p*-random stopping time set for a k-monotone p* | PLS · p*-random stopping time set | approximate uniformity: \Omega(m_0 / (k\log^2n)) | Helped |
| Use the recursive construction with \widetilde{U}(\mathcal{L}) = 2k | PLS · Constructed PLS instance | worst-case squared error: O(1/k) | Helped |
Surprising findings
- An instance family with approximate uniformity tending to infinity still admits O(1/U~) error, so 1/U~^2 cannot be improved to 1/log U~ in general.
Limitations
- Upper and lower instance-dependent bounds do not match in general.
- Analysis focuses on mean prediction; extensions to general functions are only sketched.
Experimental setup
Metrics: worst-case squared error
Baselines: fully-selective forecaster (Drucker)
Builds on: selective prediction (density prediction game) Drucker's O(1/log n) selective mean prediction
Closest papers by meaning
- Real-Time Selection Under General Constraints via Predictive Inference (NeurIPS 2024 · similarity 0.83)
- Compute-Constrained Data Selection (ICLR 2025 · similarity 0.82)
- Online Linear Regression in Dynamic Environments via Discounting (ICML 2024 · similarity 0.82)
- Cherry-Picking in Time Series Forecasting: How to Select Datasets to Make Your Model Shine (AAAI 2025 · similarity 0.82)
- Mixture of Online and Offline Experts for Non-Stationary Time Series (AAAI 2025 · similarity 0.82)
- Conditional Forecasts and Proper Scoring Rules for Reliable and Accurate Performative Predictions (NeurIPS 2025 · similarity 0.82)
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.