Dynamic Trace Estimation
Authors: Prathamesh Dharangutte, Christopher Musco
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We support our theory with empirical results, showing significant computational improvements on three applications in machine learning and network science: tracking moments of the Hessian spectral density during neural network optimization, counting triangles, and estimating natural connectivity in a dynamically changing graph. |
| Researcher Affiliation | Academia | Prathamesh Dharangutte Dept.of Computer Science & Engineering New York University ptd244@nyu.edu Christopher Musco Dept.of Computer Science & Engineering New York University cmusco@nyu.edu |
| Pseudocode | Yes | Algorithm 1 Delta Shift Input: Implicit matrix-vector multiplication access to A1, ..., Am Rn n, positive integers ℓ0, ℓ, damping factor γ [0, 1]. Output: t1, . . . , tm approximating tr(A1), . . . , tr(Am). Initialize t1 1 ℓ0 Pℓ0 i=1 g T i A1gi, where g1, . . . , gℓ0 Rn are random 1 vectors for j 2 to m do Draw ℓrandom 1 vectors g1, . . . , gℓ Rn z1 Aj 1g1, . . . , zℓ Aj 1gℓ, w1 Ajg1, . . . , wℓ Ajgℓ tj (1 γ)tj 1 + 1 ℓ Pℓ i=1 g T i (wi (1 γ)zi) end for |
| Open Source Code | No | The paper does not contain an explicit statement offering access to its source code or a link to a code repository. |
| Open Datasets | Yes | The graph dataset we use is the Wikipedia vote network dataset with 7115 nodes [25, 24]. We use the road network data Gleich/minnesota (available at https://sparse.tamu.edu/Gleich/ minnesota). |
| Dataset Splits | No | The paper does not explicitly provide training/test/validation dataset splits or cross-validation setup details. |
| Hardware Specification | No | The paper does not explicitly describe the specific hardware (e.g., GPU/CPU models, memory) used for running its experiments. |
| Software Dependencies | Yes | We implement matrix vector products with H using the Py Hessian library [47] |
| Experiment Setup | No | The paper does not explicitly provide specific hyperparameter values or detailed system-level training settings in the main text. |