Online Conformal Prediction via Universal Portfolio Algorithms
Organizations: King Abdullah University of Science and Technology, Saudi Arabia · University of Pennsylvania, USA
Abstract
Online conformal prediction (OCP) seeks prediction intervals that achieve long-run coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the -pinball loss. Our first contribution is to identify linearized regret as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.
Figures & tables
| Metric | UP-OCP | KT | DtACI | SF-OGD |
|---|---|---|---|---|
| Marginal Coverage | 0.932 | 0.920 | 0.956 | 0.948 |
| Longest Err. Seq. | 4 | 15 | 6 | 3 |
| Avg. Set Size | 14.8 | 16.9 | 16.4 | |
| Median Set Size | 11.5 | 12.9 | 12.6 | 13.8 |
| 75% Quantile Size | 18.8 | 24.9 | 21.8 | 21.5 |
| 90% Quantile Size | 32.3 | 32.5 | 32.3 |
Appendix figures & tables60 assets
Supplementary material from the paper’s appendix.
Appendix
| UP | KT | DtACI | SFOGD (lr=25) | P Ctrl (lr=0.1) | PI Ctrl (lr=0.1) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.932 | 0.92 | 0.956 | 0.948 | 0.942 | 0.941 |
| Longest err sequence | 4 | 15 | 6 | 3 | 7 | 5 |
| Average set size | 14.8 | 16.9 | 16.4 | 16.8 | 16.1 | |
| Median set size | 11.5 | 12.9 | 12.6 | 13.8 | 13.1 | 13.2 |
| 75% quantile set size | 18.8 | 24.9 | 21.8 | 21.5 | 21.5 | 20.9 |
| 90% quantile set size | 32.3 | 32.5 | 32.3 | 32.4 | 32 |
| UP | KT | DtACI | SFOGD (lr=25) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.1) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.932 | 0.915 | 0.958 | 0.945 | 0.945 | 0.941 |
| Longest err sequence | 2 | 16 | 4 | 4 | 2 | 5 |
| Average set size | 21.6 | 24.4 | 23.7 | 22.8 | 23.2 | |
| Median set size | 11.7 | 14.5 | 14 | 13.8 | 13 | 13.7 |
| 75% quantile set size | 27.3 | 39.8 | 55.8 | 36.9 | 29.2 | 33.3 |
| 90% quantile set size | 60.1 | 58.8 | 59 | 63.7 | 59.8 |
| UP | KT | DtACI | SFOGD (lr=100) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.5) | |
| Marginal coverage | 0.931 | 0.919 | 0.962 | 0.947 | 0.946 | 0.946 |
| Longest err sequence | 3 | 18 | 4 | 4 | 3 | 3 |
| Average set size | 82.8 | 99.4 | 102 | 88.9 | 89.3 | |
| Median set size | 49.1 | 57.2 | 60.4 | 57.5 | 51.5 | 51 |
| 75% quantile set size | 97.4 | 113 | 274 | 117 | 107 | 108 |
| 90% quantile set size | 208 | 276 | 288 | 234 | 239 |
| UP | KT | DtACI | SFOGD (lr=100) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.5) | |
| Marginal coverage | 0.932 | 0.925 | 0.952 | 0.948 | 0.946 | 0.946 |
| Longest err sequence | 2 | 17 | 5 | 4 | 2 | 2 |
| Average set size | 86.7 | 98.5 | 95.8 | 91.8 | 90.4 | |
| Median set size | 67.8 | 90.6 | 79.2 | 86.1 | 74.4 | 72 |
| 75% quantile set size | 121 | 137 | 133 | 132 | 124 | 126 |
| 90% quantile set size | 173 | 169 | 171 | 176 | 178 |
| UP | KT | DtACI | SFOGD (lr=1.0) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.5) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.933 | 0.927 | 0.939 | 0.95 | 0.95 | 0.95 |
| Longest err sequence | 3 | 7 | 6 | 2 | 1 | 2 |
| Average set size | 0.507 | 0.518 | 0.561 | 0.528 | 0.533 | |
| Median set size | 0.487 | 0.506 | 0.53 | 0.552 | 0.524 | 0.525 |
| 75% quantile set size | 0.593 | 0.572 | 0.563 | 0.664 | 0.637 | 0.65 |
| 90% quantile set size | 0.715 | 0.635 | 0.619 | 0.772 | 0.742 | 0.748 |
| UP | KT | DtACI | SFOGD (lr=100) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.5) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.931 | 0.928 | 0.942 | 0.95 | 0.95 | 0.95 |
| Average set size | 21.1 | 26.9 | 28.6 | 22.8 | 22.8 | |
| Median set size | 17.9 | 27.6 | 26.4 | 27.7 | 21.9 | 21.5 |
| 75% quantile set size | 34.1 | 32.1 | 33.2 | 40 | 34.9 | 34.9 |
| 90% quantile set size | 43.2 | 34.5 | 50.4 | 41.8 | 41.9 | |
| 95% quantile set size | 48.3 | 35.3 | 57.8 | 45 | 45.1 |
| UP | KT | DtACI | SFOGD (lr=100) | P Ctrl (lr=0.1) | PI Ctrl (lr=0.1) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.952 | 0.93 | 0.958 | 0.946 | 0.949 | 0.949 |
| Average set size | 592 | 596 | 694 | 566 | 567 | |
| Median set size | 500 | 574 | 494 | 691 | 531 | 534 |
| 75% quantile set size | 746 | 724 | 665 | 841 | 692 | 694 |
| 90% quantile set size | 1070 | 892 | 962 | 882 | 880 | |
| 95% quantile set size | 1320 | 994 | 1050 | 1000 | 1010 |
| UP | KT | DtACI | SFOGD (lr=100) | P Ctrl (lr=0.5) | PI Ctrl (lr=0.5) | |
|---|---|---|---|---|---|---|
| Marginal coverage | 0.951 | 0.913 | 0.963 | 0.927 | 0.947 | 0.947 |
| Average set size | 433 | 451 | 467 | 429 | 429 | |
| Median set size | 292 | 308 | 406 | 324 | 285 | 285 |
| 75% quantile set size | 624 | 692 | 790 | 626 | 626 | |
| 90% quantile set size | 1020 | 1040 | 1090 | 1020 | 1020 | |
| 95% quantile set size | 1320 | 1360 | 1260 | 1310 | 1310 |
Conformal Prediction
Conformal prediction wraps predictive models with calibrated sets or intervals that provide statistical coverage guarantees.
See all 393 papers