Research map / Learning theory and algorithms / Matrix and tensor methods
Computing Approximate $\ell_p$ Sensitivities
Swati Padmanabhan, David Woodruff, Qiuyi Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use fast total-sensitivity approximation instead of brute-force over all sensitivities | l_p total sensitivity estimation · wine, p=1 | runtime (s): 667 -> 105 | Improved |
| use fast total-sensitivity approximation instead of brute-force | l_p total sensitivity estimation · wine, p=1.5 | runtime (s): 673 -> 131 | Improved |
| use fast total-sensitivity approximation instead of brute-force | l_p total sensitivity estimation · wine, p=2.5 | runtime (s): 693 -> 209 | Improved |
| use fast total-sensitivity approximation instead of brute-force | l_p total sensitivity estimation · wine, p=3 | runtime (s): 686 -> 192 | Improved |
| use fast approximation instead of exact brute-force for total sensitivity | l_p total sensitivity estimation · wine, p=1 | total sensitivity estimate: 5.2 -> 6.4 | Hurt |
| use fast approximation instead of exact brute-force for total sensitivity | l_p total sensitivity estimation · wine, p=3 | total sensitivity estimate: 7.2 -> 8.9 | Hurt |
| compare empirical total sensitivity to theoretical upper bound | wine dataset · wine, p=3 | total sensitivity: 52.4 -> 7.2 | Improved |
| increase approximation parameter alpha to 40 for l_p sensitivity approximation | fast l_p sensitivity approximation · wine | accuracy vs runtime: 16x accuracy deterioration for 40x faster | Mixed |
| use sensitivity sampling instead of Lewis weight sampling | row sampling for l_p regression · UCI datasets | sampling bound size: 2-5x better | Improved |
Closest papers by meaning
- Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation (ICML 2024 · similarity 0.90)
- Coresets for Multiple $\ell_p$ Regression (ICML 2024 · similarity 0.85)
- Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy (NeurIPS 2025 · similarity 0.84)
- Turnstile $\ell_p$ leverage score sampling with applications (ICML 2024 · similarity 0.84)
- Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond (ICML 2024 · similarity 0.83)
- Beyond Worst-Case Dimensionality Reduction for Sparse Vectors (ICLR 2025 · similarity 0.83)
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.
