Accurate Coresets for Latent Variable Models and Regularized Regression

Accurate coresets are a weighted subset of the original dataset, ensuring a model trained on the accurate coreset maintains the same level of accuracy as a model trained on the full dataset. Primarily, these coresets have been studied for a limited range of machine learning models. In this paper, we introduce a unified framework for constructing accurate coresets. Using this framework, we present accurate coreset construction algorithms for general problems, including a wide range of latent variable model problems and ℓp-regularized ℓp-regression. For latent variable models, our coreset size is Oleft(poly(k)right), where k is the number of latent variables. For ℓp-regularized ℓp-regression, our algorithm captures the reduction of model complexity due to regularization, resulting in a coreset whose size is always smaller than dp for a regularization parameter λ > 0. Here, d is the dimension of the input points. This inherently improves the size of the accurate coreset for ridge regression. We substantiate our theoretical findings with extensive experimental evaluations on real datasets.