Stratified sampling meets machine learning
Kevin Lang, Edo Liberty, Konstantin Shmakov · 2016
inc.com This paper investigates the practice of non-uniformly sam-pling records from a database. The goal is to evaluate future aggregate queries as accurately as possible while maintain-ing a fixed sampling budget. We formalize this as a machine learning problem in the PAC model. The model learned corresponds to sampling proba-bilities of individual records and a training set is obtained from previously issued queries to the database. We provide an efficient and simple regularized Empirical Risk Minimiza-tion (ERM) algorithm for this problem along with a theo-retical generalization result for it. Our experiments show that model accuracy improves with more training data, that insufficient training data can cause overfitting and that careful regularization is key. These give important practical insights and strengthen the parallels to other machine learning tasks. We report extensive results for both synthetic and real datasets that significantly im-prove over both uniform sampling and standard stratified sampling. 1.