Research map / Learning theory and algorithms / Matrix and tensor methods
Dynamic Trace Estimation
Prathamesh Dharangutte, Christopher P Musco
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 DeltaShift instead of independent Hutchinson estimators | trace estimation · Hessian T_1(H), Table 1 | average relative error: 2.5e-02 -> 1.7e-02 | Improved |
| use DeltaShift instead of Hutchinson | trace estimation · Hessian T_3(H), Table 2 | average relative error: 7.7e-02 -> 6.1e-02 | Improved |
| use DeltaShift instead of Hutchinson | trace estimation · Hessian T_2(H), Table 1 | average relative error: 1.2e-06 -> 8.0e-07 | Improved |
| use DeltaShift instead of NoRestart (damping and restart-free variance reduction) (ablation) | trace estimation · Hessian T_1(H), Table 2 | average relative error: 5.0e-02 -> 1.5e-02 | Improved |
| use DeltaShift instead of NoRestart (ablation) | trace estimation · Hessian T_5(H), Table 1 | average relative error: 4.3e-02 -> 1.9e-02 | Improved |
| NoRestart variance reduction vs plain Hutchinson (ablation) | trace estimation · Hessian T_1(H), Table 1 | average relative error: 2.5e-02 -> 3.7e-02 | Hurt |
| DeltaShift vs Hutchinson with faster-changing Hessian (more training progress) | trace estimation · Hessian spectral density | relative improvement | Mixed |
| DeltaShift vs Hutchinson and NoRestart with small rank-1 perturbations | trace estimation · synthetic, n=2000, 100 steps | scaled absolute error | Improved |
| DeltaShift vs baselines with large rank-25 perturbations | trace estimation · synthetic, n=2000, 100 steps | scaled absolute error | Improved |
| DeltaShift vs Hutchinson and NoRestart at lower query budgets Q | trace estimation · synthetic data | average relative error | Improved |
| DeltaShift vs Hutchinson and NoRestart for triangle counting | trace estimation · Wikipedia vote network, 7115 nodes | trace error | Improved |
| add low-rank nuclear-norm exploitation (DeltaShift++ over DeltaShift) (ablation) | DeltaShift · natural connectivity, Gleich/minnesota | error | Improved |
Closest papers by meaning
- Optimal Query Complexities for Dynamic Trace Estimation (NeurIPS 2022 · similarity 0.89)
- Optimal Sketching for Trace Estimation (NeurIPS 2021 · similarity 0.88)
- Change Point Localization and Inference in Dynamic Multilayer Networks (ICLR 2026 · similarity 0.84)
- Low-Rank Matrix Estimation in the Presence of Change-Points (JMLR 2024 · similarity 0.84)
- Connectivity Shapes Implicit Regularization in Matrix Factorization Models for Matrix Completion (NeurIPS 2024 · similarity 0.82)
- Determinant Estimation under Memory Constraints and Neural Scaling Laws (ICML 2025 · similarity 0.82)
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.
