On Coresets for Regularized Loss Minimization
This work addresses the challenge of scalable machine learning for practitioners dealing with big data by providing efficient sampling-based algorithms, though it is incremental as it builds on existing coreset theory.
The paper tackles the problem of efficiently constructing coresets for regularized loss minimization in large-scale data settings, showing that a uniform sample of size O(d√n) is sufficient with high probability for logistic regression and SVM with common regularizers, and proving tightness and near-optimality of this bound.
We design and mathematically analyze sampling-based algorithms for regularized loss minimization problems that are implementable in popular computational models for large data, in which the access to the data is restricted in some way. Our main result is that if the regularizer's effect does not become negligible as the norm of the hypothesis scales, and as the data scales, then a uniform sample of modest size is with high probability a coreset. In the case that the loss function is either logistic regression or soft-margin support vector machines, and the regularizer is one of the common recommended choices, this result implies that a uniform sample of size $O(d \sqrt{n})$ is with high probability a coreset of $n$ points in $\Re^d$. We contrast this upper bound with two lower bounds. The first lower bound shows that our analysis of uniform sampling is tight; that is, a smaller uniform sample will likely not be a core set. The second lower bound shows that in some sense uniform sampling is close to optimal, as significantly smaller core sets do not generally exist.