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 $\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 $μ_\mathbf{y}(\mathbf{X})$, first defined in (Munteanu, 2018). We give an $\tildeΩ(\frac{d}{ε^2})$ space complexity lower bound in the regime $μ_\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Ω(d\cdot μ_\mathbf{y}(\mathbf{X}))$ space lower bound when $ε$ is constant, showing that the dependency on $μ_\mathbf{y}(\mathbf{X})$ is not an artifact of mergeable coresets. Finally, we refute a prior conjecture that $μ_\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.