Title: Online Learning for Distribution-Free Prediction,
Abstract: 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.