Dynamic Trace Estimation
Dec 6, 2021
Speakers
Prathamesh Dharangutte
Speaker · 0 followers
Christopher Musco
Speaker · 0 followers
About
We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our goal is to maintain an accurate approximation to A's trace using as few multiplications as possible. We present a practical algorithm for solving this problem and prove that, in a natural setting, its complexity is quadratically better than the standard solution of repeatedly applying Hutchinson's stochastic trace estimator. We also provide an improved algorithm assuming additional common assumptions on A's dynamic updates. 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.We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our goal is to maintain an accurate approximation to A's trace using as few multiplications as possible. We present a practical algorithm for solving this problem and prove that, in a natural setting, its complexity is quadratically better than the standard solution of repeatedly applying Hutchinson's stochastic trace est…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Diversity is All You Need to Improve Bayesian Model Averaging
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Formalizing the Generalization-Forgetting Trade-off in Continual Learning
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Sharpness-Aware Minimization for Robust Molecular Dynamics Simulations
Watch later
Total of 1 viewers voted for saving the presentation to eternal vault which is 0.1%
Differentially Private Empirical Risk Minimization under the Fairness Lens
Watch later
Cuong Tran, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
AI workloads inside databases
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning Adaptive Control Flow in Transformers for Improved Systematic Generalization
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%