Among the current approaches to making statistical methods scalable to large datasets, randomized algorithms have recently gained popularity. The randomized algorithms approach the problem by constructing a substantially smaller sketch of the large scale data at hand. Then, existing methods are applied to the sketch to reduce computation cost. When the sketch keeps the most relevant information, the result computed from it should remain close to the result from the original dataset. There are a few ways to construct a sketch of a large data set. One approach is to draw subsamples with respect to some carefully designed probability, which will select informative samples with larger probability. These sampling probabilities include the importance sampling in matrix multiplication [1]}, the leverage sampling for least squares regression [2]}, [3]}, the subspace sampling for low rank matrix construction [4]}, etc. Effective sampling probabilities have also been proposed for logistic regression [5]}, [6]} and generalized linear models [7]} to minimize the asymptotic variance of the estimator. An alternative way towards sketching is to mix the original data with a random projection and draw samples from the projected data [8]}, [9]}.
