Sparsifying Generalized Linear Models
summary
Proves that sums F(x)=Σ f_i(<a_i,x>) with symmetric, monotone, mild growth f_i admit (1+ε)-approximate sparsifiers of support size about n/ε^2 times polylog factors ((log n)^{O(1)}), covering ℓ_p (p∈(0,2]) and Huber/min{|z|^p,|z|^2}; gives an efficient randomized algorithm (samples across logarithmic scales using approximate Lewis weights, then reweights) with runtime near-linear in input sparsity plus õ(1) linear-system work, and uses a contractive‑map existence proof plus chaining to get high‑probability uniform guarantees and faster L_p regression reductions.
AI-written summary · about
chapters (9)
- 0:00Introduction to sparsification
- 2:50Applications in regression
- 5:03Graph and spectral sparsifiers
- 6:29Generalized linear models
- 13:47Limits of sparsification
- 19:23Algorithmic optimization
- 29:45Main theorem and conditions
- 36:03Building the sparsifiers
- 50:32Future work and discussion
related talks
44mActive Regression via Linear-Sample Sparsification
01h 06mAnalytic Methods for Supervised Learning III
30mComputational Barriers For Learning Some Generalized Linear Models
01h 03mSparsifying Sums of Norms
42mToward Understanding the Extrapolation of Nonlinear Models to Unseen Domains or the Whole Domain
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 05mRecovering Hidden Sparsity via Sum of Squares
01h 10mOptimization II