The Space Complexity of Approximating Logistic Loss

We provide space complexity lower bounds for data structures that approximate logistic loss up to ε-relative error on a logistic regression problem with data X ∈ ℝn × d and labels y ∈ -1,1d. The space complexity of existing coreset constructions depend on a natural complexity measure μy(X), first defined in (Munteanu, 2018). We give an tildeOmega(fracdε2) space complexity lower bound in the regime μy(X) = O(1) that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general tildeOmega(d· μy(X)) space lower bound when ε is constant, showing that the dependency on μy(X) is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that μy(X) is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.