The Space Complexity of Approximating Logistic Loss

Gregory Dexter, Petros Drineas, Rajiv Khanna

We provide space complexity lower bounds for data structures that approximate logistic loss up to $\epsilon$-relative error on a logistic regression problem with data $\mathbf{X} \in \mat…