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±ϵ) relative error with Õ(d ·μ_y(X)^2/ϵ^2) points, where μ_y(X) is a natural complexity measure of the data matrix X ∈ℝ^n × d and label vector y ∈{-1,1}^n, introduced by Munteanu et al. 2018. Our result is based on subsampling data points with probabilities proportional to their ℓ_1 Lewis weights. It significantly improves o…