Fast Sampling-Based Sketches for Tensors
Authors: William Joseph Swartworth, David Woodruff
ICML 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We evaluate the correctness of the ℓ0 samplers. Our ℓ0-sampler is theoretically guaranteed to output a uniformly random entry of the support, up to some constant factor. That is, the probability we output a fixed entry of the support of a tensor X is [ c1 |supp(X)|, c2 |supp(X)|] for some absolute constants c1 and c2. In order to keep our analysis simple, the constants c1 and c2 gotten from unwinding our proof are more extreme than necessary. We remedy this by empirically showing that our sampler is in fact much closer to uniform. All of our experiments suggest that our ℓ0 sampling procedure behaves very nearly perfectly on the tensors described above. All experiments are accurate to within a few percent of what one would expect for uniform sampling. See section C in the appendix for tables showing our experimental data. |
| Researcher Affiliation | Academia | William Swartworth 1 David Woodruff 1 1Carnegie Mellon University. |
| Pseudocode | No | The paper does not contain explicit pseudocode or algorithm blocks, only mathematical descriptions of constructions and proofs. |
| Open Source Code | Yes | The code for the experiments, along with additional implementations of our sketch are available at https:// github.com/wswartworth/tensor Sampling. |
| Open Datasets | No | The paper describes custom-generated data for experiments (e.g., "disjoint rectangle support", "rectangle B... with an additional ... random entries") rather than using a named publicly available dataset with a specific access link or formal citation. |
| Dataset Splits | No | The paper mentions running "1000 trials" on tensors of a certain shape but does not specify explicit training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not specify any particular hardware components such as GPU or CPU models used for running the experiments. |
| Software Dependencies | No | The paper does not provide specific software dependencies with version numbers (e.g., Python 3.8, PyTorch 1.9). |
| Experiment Setup | Yes | We choose our ℓ0 sampler to have 10 buckets at each sampling level. For an N N N tensor X our sampling rates begin at 1/N 3 and increase in powers of 5. ... All experiments are carried out on a tensor of shape 40 40 40 for 1000 trials. |