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 \mathbb{ R}^{ n \times d}$ and labels $\mathbf{ y} \in \{ -1,1\}^d$. The space complexity of existing coreset constructions depend on a natural complexity measure $\mu_\mathbf{ y}(\mathbf{ X})$, first defined in (Munteanu, 2018). We give an $\tilde{ \Omega}(\frac{ d}{ \epsilon^2})$ space complexity lower bound in the regime $\mu_\mathbf{ y}(\mathbf{ X}) = O(1)$ that shows existing coresets are optimal in this regime up to lower order factors. We also prove a general $\tilde{ \Omega}(d\cdot \mu_\mathbf{ y}(\mathbf{ X}))$ space lower bound when $\epsilon$ is constant, showing that the dependency on $\mu_\mathbf{ y}(\mathbf{ X})$ is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that $\mu_\mathbf{ y}(\mathbf{ X})$ is hard to compute by providing an efficient linear programming formulation, and we empirically compare our algorithm to prior approximate methods.
Categories: cs.DS cs.LG