# The Space Complexity of Approximating Logistic Loss

arXiv: https://arxiv.org/abs/2412.02639 · HTML: https://mlsanity.com/paper/2412.02639/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 3 Dec 2024.

## Builds on (most cited first, 8 of 8)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets for Classification -- Simplified and Strengthened](https://mlsanity.com/paper/2106.04254/) (2021)
- [Oblivious sketching for logistic regression](https://mlsanity.com/paper/2107.06615/) (2021)
- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Lower bounds for oblivious subspace embeddings](https://mlsanity.com/paper/1308.3280/) (2013)
- [Tight Bounds for the Subspace Sketch Problem with Applications](https://mlsanity.com/paper/1904.05543/) (2019)
- [Optimal bounds for ℓp sensitivity sampling via ℓ2 augmentation](https://mlsanity.com/paper/2406.00328/) (2024)

## Abstract (arXiv)

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.