Online Learning for Distribution-Free Prediction
This work provides a computationally efficient and distribution-free solution for online prediction, which is incremental as it builds on existing split conformal approaches.
The authors tackled the problem of online prediction for large or streaming datasets by developing a covariance-fitting method that achieves linear runtime, constant memory, and distribution-free confidence intervals, demonstrating its effectiveness on real and synthetic data.
We develop an online learning method for prediction, which is important in problems with large and/or streaming data sets. We formulate the learning approach using a covariance-fitting methodology, and show that the resulting predictor has desirable computational and distribution-free properties: It is implemented online with a runtime that scales linearly in the number of samples; has a constant memory requirement; avoids local minima problems; and prunes away redundant feature dimensions without relying on restrictive assumptions on the data distribution. In conjunction with the split conformal approach, it also produces distribution-free prediction confidence intervals in a computationally efficient manner. The method is demonstrated on both real and synthetic datasets.