Research map / Learning theory and algorithms / Sample complexity
Optimal Query Complexities for Dynamic Trace Estimation
David Woodruff, Fred Zhang, Qiuyi Zhang
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 the binary tree summation algorithm instead of DiffSum and DeltaShift | dynamic Hutch++ trace estimation · Triangle counting on ca-GrQc and ca-HepTh with growing cliques, budget 8,000 | relative error | Improved |
| use the proposed algorithm instead of DiffSum and DeltaShift on neural network weight matrices | dynamic trace estimation · MNIST three-layer network weights, first 1,000 SGD steps, budget 50,000 | trace estimation error | Improved |
Closest papers by meaning
- Dynamic Trace Estimation (NeurIPS 2021 · similarity 0.89)
- GL-LowPopArt: A Nearly Instance-Wise Minimax-Optimal Estimator for Generalized Low-Rank Trace Regression (ICML 2025 · similarity 0.84)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.84)
- Statistical-Computational Trade-offs for Density Estimation (NeurIPS 2024 · similarity 0.84)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.83)
- Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits (ICML 2024 · similarity 0.83)
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.
