Dynamic Trace Estimation

Prathamesh Dharangutte, Christopher Musco

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    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 slightly stronger assumptions on the dynamic matrix A. 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.

    Original languageEnglish (US)
    Title of host publicationAdvances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021
    EditorsMarc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
    PublisherNeural information processing systems foundation
    Number of pages12
    ISBN (Electronic)9781713845393
    StatePublished - 2021
    Event35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online
    Duration: Dec 6 2021Dec 14 2021

    Publication series

    NameAdvances in Neural Information Processing Systems
    ISSN (Print)1049-5258


    Conference35th Conference on Neural Information Processing Systems, NeurIPS 2021
    CityVirtual, Online

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Dynamic Trace Estimation'. Together they form a unique fingerprint.

    Cite this