  In statistics and machine learning, logistic regression is a widely-used
supervised learning technique primarily employed for binary classification
tasks. When the number of observations greatly exceeds the number of predictor
variables, we present a simple, randomized sampling-based algorithm for
logistic regression problem that guarantees high-quality approximations to both
the estimated probabilities and the overall discrepancy of the model. Our
analysis builds upon two simple structural conditions that boil down to
randomized matrix multiplication, a fundamental and well-understood primitive
of randomized numerical linear algebra. We analyze the properties of estimated
probabilities of logistic regression when leverage scores are used to sample
observations, and prove that accurate approximations can be achieved with a
sample whose size is much smaller than the total number of observations. To
further validate our theoretical findings, we conduct comprehensive empirical
evaluations. Overall, our work sheds light on the potential of using randomized
sampling approaches to efficiently approximate the estimated probabilities in
logistic regression, offering a practical and computationally efficient
solution for large-scale datasets.
