Online Prediction with Limited Selectivity
This work addresses a limitation in forecasting models for scenarios where selective prediction is restricted, which is incremental as it builds on existing selective prediction frameworks.
The paper tackles the problem of selective prediction under a new constraint where forecasters can only start predictions on a subset of the time horizon, introducing a model called Prediction with Limited Selectivity (PLS). It studies optimal prediction error through instance-dependent bounds and average-case analysis, showing these bounds match with high probability for randomly-generated instances.
Selective prediction [Dru13, QV19] models the scenario where a forecaster freely decides on the prediction window that their forecast spans. Many data statistics can be predicted to a non-trivial error rate without any distributional assumptions or expert advice, yet these results rely on that the forecaster may predict at any time. We introduce a model of Prediction with Limited Selectivity (PLS) where the forecaster can start the prediction only on a subset of the time horizon. We study the optimal prediction error both on an instance-by-instance basis and via an average-case analysis. We introduce a complexity measure that gives instance-dependent bounds on the optimal error. For a randomly-generated PLS instance, these bounds match with high probability.