Skip to main content
SHARE
Publication

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression

by Agniva Chowdhury, Pradeep Ramuhalli
Publication Type
Conference Paper
Book Title
Proceedings of the 38th AAAI Conference on Artificial Intelligence
Publication Date
Page Numbers
11597 to 11605
Issue
10
Publisher Location
Washington, District of Columbia, United States of America
Conference Name
The 38th Annual AAAI Conference on Artificial Intelligence
Conference Location
Vancouver, Canada
Conference Sponsor
Association for the Advancement of Artificial Intelligence (AAAI)
Conference Date
-

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.