Research map / Learning theory and algorithms / Matrix and tensor methods

Turnstile $\ell_p$ leverage score sampling with applications

ICML 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Low-rank approximation theory · 0 citations (OpenAlex)

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.

Proposes a turnstile-stream L_{p,p} row sampler for p in [1,2] built from CountSketch with random scalings and percentile-based statistical tests, combined with ℓp conditioning to get ℓp leverage-score sampling and polynomial-size coresets for logistic and other regression losses.

Problem

Sampling rows of a matrix proportional to their ℓp norm or ℓp leverage scores (for coresets) when the matrix is given as a turnstile data stream, where entries can be updated arbitrarily; prior logistic regression sketches needed exp(1/ε) size or gave only O(1) approximations.

Approach

Generalize the turnstile L2 sampler to all p in [1,2] by thresholding CountSketch buckets via percentiles of their norms (no p-stable or AMS sketches), recovering perturbed rows via a median-based representative, and post-multiplying the sketch by a conditioning matrix to obtain ℓp leverage score sampling; the sketch is then used to extract a coreset in postprocessing.

Key results

• Turnstile sampler for logistic regression gives a (1+eps)-coreset with polynomial sketch size, improving on the exp(1/eps) size of prior work and the O(1) approximations of oblivious sketches.
• Experiments on Covertype, Webspam, and KDDCup show the turnstile sampler clearly outperforms oblivious sketching and performs close to offline leverage score sampling for logistic and l1 regression.
• Theorem gives sample size in [k,2k] with sampling probability at least min{1, k||a_i||_p^p/||A||_p^p} and weights within (1±eps) of inverse inclusion probability.

Measured effects reported in the paper

Surprising findings

• Polynomial-size turnstile coresets for logistic regression are possible despite prior impossibility results for pure oblivious sketches, because the sketch is post-processed (cherry-picked) rather than used as the final summary.

Limitations

• Robustness to perturbations must be verified case by case; only linear, ReLU, probit, and logistic losses (and their l_p generalizations) are covered.
• p>2 requires near-linear sketch size Omega(n^{1-2/p}), so the framework is limited to p in [1,2].
• Conditioning matrices with near-optimal (alpha*beta)^p are not constructible in turnstile streams; current bounds carry extra d factors.

Experimental setup

Datasets: Covertype Webspam KDDCup

Benchmarks: Covertype Webspam KDDCup

Metrics: approximation ratio f(z~)/f(z_opt)

Baselines: plain oblivious sketching plain l_p leverage score sampling exp(1/eps) logistic regression sketch O(1)-approximation oblivious logistic sketch

Builds on: L2 turnstile row sampler CountSketch Lewis weights/ell_p leverage score sampling oblivious l_p subspace embeddings

Closest papers by meaning

• Nearly Linear Row Sampling Algorithm for Quantile Regression (ICML 2020 · similarity 0.88)
• Relating Leverage Scores and Density using Regularized Christoffel Functions (NeurIPS 2018 · similarity 0.86)
• Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures (ICML 2025 · similarity 0.84)
• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers (ICLR 2024 · similarity 0.84)
• Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters (NeurIPS 2024 · similarity 0.84)
• Query Lower Bounds for Diffusion Sampling (NeurIPS 2026 · similarity 0.83)