# Sparsifying generalized linear models

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Nov 2023.

## Built on by (most cited first, 3 of 3)

- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

We consider the sparsification of sums F : ℝn → ℝ where F(x) = f1(langle a1,xrangle) + cdots + fm(langle am,xrangle) for vectors a1,ldots,am ∈ ℝn and functions f1,ldots,fm : ℝ → ℝ_+. We show that (1+varepsilon)-approximate sparsifiers of F with support size fracnvarepsilon2 (log fracnvarepsilon)O(1) exist whenever the functions f1,ldots,fm are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each fi can be evaluated efficiently. Our results generalize the classic case of ℓp sparsification, where fi(z) = |z|p, for p ∈ (0, 2], and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., fi(z) = min|z|p, |z|2 for 0 < p ≤ 2. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including ℓp regression for p ∈ (1, 2] to high accuracy, via solving (log n)O(1) sparse regression instances with m ≤ n(log n)O(1), plus runtime proportional to the number of nonzero entries in the vectors a1, dots, am.