Since the seminal works of [1]}, [2]}, [3]} for matrix multiplication and approximation, the idea of randomized algorithm has been successfully applied to optimization [4]}, [5]}, low rank matrix estimation [6]}, [7]}, least squares regression [8]}, nonparametric kernel regression [9]}, etc. These algorithms are able to yield comparatively accurate results at reduced computational and storage costs. See the references [10]}, [11]} for an overview. Most theoretical analysis of these randomized algorithms is conducted from the algorithmic perspective, where the analysis is carried out conditionally on an arbitrarily fixed dataset. Some recent works [12]}, [13]}, [14]} also draw analysis from the statistical perspective, where statistical properties such as bias and average prediction error are considered.
