Research map / Learning theory and algorithms / Sample complexity
The Space Complexity of Approximating Logistic Loss
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves space lower bounds for data structures approximating logistic loss (Ω̃(d/ε²) when μ=O(1), Ω̃(d·μ) for constant ε), and gives an LP that computes the μ complexity measure exactly.
Problem
Space complexity of data structures and coresets that approximate logistic loss to relative error, and the cost of computing the classification complexity measure μ_y(X) used in coreset bounds.
Approach
Reduces relative-error logistic loss approximation to ReLU loss and then to ℓ1-subspace embedding / INDEX lower bounds, showing existing coresets are optimal when μ=O(1); also gives an exact linear program (with binary variables in the approximate variant) for μ_y(X), refuting the hardness conjecture.
Key results
- Proves Ω̃(d/ε²) space lower bound for logistic loss ε-relative approximation when μ_y(X)=O(1), showing existing coreset sizes are optimal up to log factors.
- Proves Ω̃(d·μ_y(X)) space lower bound for constant-factor approximation, showing dependence on μ is not an artifact of mergeable coresets.
- Gives an exact LP with 2n variables and 4n constraints computing μ_y(X), and experiments show prior sketch-based upper/lower bounds on μ can be loose.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use exact LP computation on sketched data instead of sketching-based approximate upper and lower bounds | Classification complexity measure estimation · Synthetic data | agreement with full-data μ_y(X) | Helped |
| Use exact μ_y(X) calculations rather than sketching-based approximate bounds | Classification complexity measure estimation · KDDCup | tightness of μ_y(X) estimates | Helped |
Surprising findings
- Prior conjecture that μ_y(X) is hard to compute is refuted by an efficient LP formulation.
- Approximate sketch-based bounds on μ can be fairly loose compared to exact computation.
Limitations
- Gap of a factor d between coreset upper bounds and lower bounds when epsilon is constant or mu is constant respectively.
- The Ω̃(d/ε²) lower bound applies only to for-all guarantees and only in the regime mu=O(1).
Experimental setup
Datasets: synthetic Gaussian data (n=10,000, d=100) sklearn KDDCup99 continuous features (33 features)
Benchmarks: synthetic Gaussian data KDDCup99 subsets
Metrics: computed value of mu_y(X) upper and lower bounds on mu vs exact value
Baselines: approximate sketching-based estimation of mu (Mai et al. style LP with well-cond
Builds on: INDEX problem lower bound l1 subspace embedding lower bound Lewis weight sampling coresets classification complexity measure mu
Closest papers by meaning
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.85)
- Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling (NeurIPS 2026 · similarity 0.85)
- A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise (NeurIPS 2024 · similarity 0.84)
- Sample complexity of stochastic optimization with integer variables (NeurIPS 2026 · similarity 0.84)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.84)
- Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.