Timezone: »

 
Coresets for Classification – Simplified and Strengthened
Tung Mai · Anup Rao · Cameron Musco

Sat Jul 24 12:37 PM -- 12:42 PM (PDT) @
in Subset Selection in Machine Learning: From Theory to Applications »
We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves $(1\pm \epsilon)$ relative error with $\tilde O(d \cdot \mu_y(X)^2/\epsilon^2)$ points, where $\mu_y(X)$ is a natural complexity measure of the data matrix $X \in \R^{n \times d}$ and label vector $y \in \{-1,1\}^n$, introduced in \cite{munteanu2018coresets}. Our result is based on subsampling data points with probabilities proportional to their \emph{$\ell_1$ Lewis weights}. It significantly improves on existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used in multiple training scenarios.

Author Information

Tung Mai (Adobe Research)
Anup Rao (Adobe Research)
Cameron Musco (UMass)

More from the Same Authors