Application Of Sketching Algorithm In Conformal Prediction

In the context of the big data trend,data is precious and huge.The increasing data scale brings us great storage and computing pressure.In order to ease the computing load,people gradually focus on data compression technology.Sketching is one of these data compression techniques,it can compress the source data matrix into a smaller matrix within a controllable range,and the subsequent calculation and analysis are performed on the compressed data,which reduces the calculation and improves the efficiency.Many scholars have made important contributions to the theoretical research of sketching algorithm.However,this paper focuses on the application of sketching algorithm.The method of "sketch and solve" is used to combine sketching with conformal prediction,that is,take a sketch first,and then perform conformal prediction.And the framework of "sketched conformal prediction" algorithm is proposed.Conformal prediction is a distribution-free interval estimation method,which can give a relatively accurate prediction interval,but the calculation is too complicated,so it is not suitable for large data sets.The sketched conformal prediction can improve the computational efficiency based on the sketching algorithm and give the appropriate prediction interval.In this paper,simulated and real data experiments are conducted in low and high dimensional settings respectively,considering three types of sketching matrices:Gaussian,CW and Hadamard.The conformal prediction fitting algorithm uses least squares and ridge regression respectively,and the sketched conformal prediction framework correspondingly uses complete sketched conformal prediction and classical sketched ridge regression conformal prediction.The results show that,compared with conformal prediction,the sketched conformal prediction has a great improvement in operation time,and gives an appropriate prediction interval with reasonable errors.In the low-dimensional setting,conformal prediction always undercovers when the data size and data dimension are large,while sketched conformal prediction can provide prediction intervals with more appropriate coverage levels while reducing the sample size.However,in high-dimensional settings,conformal prediction is prone to over-coverage.In this case,the sketched conformal prediction algorithm can be used to increase the sample size,and the resulting prediction interval will be shorter without introducing too much error.In conclusion,the proposed sketched conformal prediction algorithm improves conformal prediction to some extent,and is verified on simulated and real data sets.