Sharper Bounds for $\ell_p$ Sensitivity Sampling
Authors: David Woodruff, Taisuke Yasuda
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we show the first bounds for sensitivity sampling for βπsubspace embeddings for π = 2 that improve over the general Sπbound, achieving a bound of roughly S2/πfor 1 π< 2 and S2 2/πfor 2 < π< . For 1 π< 2, we show that this bound is tight, in the sense that there exist matrices for which S2/πsamples is necessary. Furthermore, our techniques yield further new results in the study of sampling algorithms, showing that the root leverage score sampling algorithm achieves a bound of roughly πfor 1 π< 2, and that a combination of leverage score and sensitivity sampling achieves an improved bound of roughly π2/πS2 4/πfor 2 < π< . Our sensitivity sampling results yield the best known sample complexity for a wide class of structured matrices that have small βπsensitivity. ... Our work introduces a new analysis for sensitivity sampling for βπsubspace embeddings, which breaks a previous general sampling barrier of π(π 2Sπ(A)π) samples via a simple union bound argument, to obtain an improved bound of π(π 2Sπ(A)2/π) samples for π< 2 and π(π 2Sπ(A)2 2/π) samples for π> 2. |
| Researcher Affiliation | Academia | 1Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, US. Correspondence to: Taisuke Yasuda <taisukey@cs.cmu.edu>. |
| Pseudocode | No | The paper describes algorithmic procedures in prose but does not include any explicitly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not contain any statement about releasing source code for the described methodology, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on a specific dataset, therefore no public dataset access information is provided. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments or data processing, thus no training/test/validation dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments, therefore no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no specific experimental setup details or hyperparameters are provided. |