Optimal Sketching for Trace Estimation
Authors: Shuli Jiang, Hai Pham, David Woodruff, Richard Zhang
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, our experiments demonstrate the superior performance of our sketch over the adaptive Hutch++ algorithm, which is less parallelizable, as well as over the non-adaptive Hutchinson s method. |
| Researcher Affiliation | Collaboration | Shuli Jiang Robotics Institute Carnegie Mellon University shulij@andrew.cmu.edu Hai Pham Language Technologies Institute Carnegie Mellon University htpham@cs.cmu.edu David P. Woodruff Computer Science Department Carnegie Mellon University dwoodruf@cs.cmu.edu Qiuyi (Richard) Zhang Google Brain qiuyiz@google.com |
| Pseudocode | Yes | Algorithm 1 Hutch++: Stochastic trace estimation with adaptive matrix-vector queries ... Algorithm 2 NA-Hutch++: Stochastic trace estimation with non-adaptive matrix-vector queries |
| Open Source Code | Yes | All the code is included in the supplementary material and will be publicly released. Our code is available at: https://github.com/11hifish/OptSketchTraceEst |
| Open Datasets | Yes | All datasets used in the experiments are public. The links to the datasets are provided in the footnote in Section 5. |
| Dataset Splits | No | The paper mentions conducting '100 random runs' but does not specify how the datasets were split into training, validation, or test sets. |
| Hardware Specification | Yes | All experiments are conducted on machines with 40 CPU cores. |
| Software Dependencies | No | The paper mentions 'Python multiprocessing package' and 'sparse_dot_mkl' but does not provide specific version numbers for these or other key software dependencies like Python itself or any machine learning frameworks. |
| Experiment Setup | Yes | We set c1 = c3 = 1/4 and c2 = 1/2 as [16] suggests. For all of our experiments, we fix the error parameter ϵ = 0.01 and measure the performance of each algorithm with {10, 30, 50, . . . , 130, 150} queries on synthetic, roget and precipitation, and with {100, 200, . . . , 700, 800} queries on arxiv_cm... with varying max moments {10, 15, . . . , 30} and 30 matrix-vector queries. |