Asynchronous Randomized Trace Estimation

Vasileios Kalantzis, Shashanka Ubaru, Chai Wah Wu, Georgios Kollias, Lior Horesh
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:4294-4302, 2024.

Abstract

Randomized trace estimation is a popular technique to approximate the trace of an implicitly-defined matrix $A$ by averaging the quadratic form $x’Ax$ across several samples of a random vector $x$. This paper focuses on the application of randomized trace estimators on asynchronous computing environments where the quadratic form $x’Ax$ is computed partially by observing only a random row subset of $A$ for each sample of the random vector $x$. Our asynchronous framework treats the number of rows, as well as the row subset observed for each sample, as random variables, and our theoretical analysis establishes the variance of the randomized estimator for Rademacher and Gaussian samples. We also present error analysis and sampling complexity bounds for the proposed asynchronous randomized trace estimator. Our numerical experiments illustrate that the asynchronous variant can be competitive even when a small number of rows is updated per each sample.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-kalantzis24a, title = {Asynchronous Randomized Trace Estimation}, author = {Kalantzis, Vasileios and Ubaru, Shashanka and Wah Wu, Chai and Kollias, Georgios and Horesh, Lior}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {4294--4302}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/kalantzis24a/kalantzis24a.pdf}, url = {https://proceedings.mlr.press/v238/kalantzis24a.html}, abstract = {Randomized trace estimation is a popular technique to approximate the trace of an implicitly-defined matrix $A$ by averaging the quadratic form $x’Ax$ across several samples of a random vector $x$. This paper focuses on the application of randomized trace estimators on asynchronous computing environments where the quadratic form $x’Ax$ is computed partially by observing only a random row subset of $A$ for each sample of the random vector $x$. Our asynchronous framework treats the number of rows, as well as the row subset observed for each sample, as random variables, and our theoretical analysis establishes the variance of the randomized estimator for Rademacher and Gaussian samples. We also present error analysis and sampling complexity bounds for the proposed asynchronous randomized trace estimator. Our numerical experiments illustrate that the asynchronous variant can be competitive even when a small number of rows is updated per each sample.} }
Endnote
%0 Conference Paper %T Asynchronous Randomized Trace Estimation %A Vasileios Kalantzis %A Shashanka Ubaru %A Chai Wah Wu %A Georgios Kollias %A Lior Horesh %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-kalantzis24a %I PMLR %P 4294--4302 %U https://proceedings.mlr.press/v238/kalantzis24a.html %V 238 %X Randomized trace estimation is a popular technique to approximate the trace of an implicitly-defined matrix $A$ by averaging the quadratic form $x’Ax$ across several samples of a random vector $x$. This paper focuses on the application of randomized trace estimators on asynchronous computing environments where the quadratic form $x’Ax$ is computed partially by observing only a random row subset of $A$ for each sample of the random vector $x$. Our asynchronous framework treats the number of rows, as well as the row subset observed for each sample, as random variables, and our theoretical analysis establishes the variance of the randomized estimator for Rademacher and Gaussian samples. We also present error analysis and sampling complexity bounds for the proposed asynchronous randomized trace estimator. Our numerical experiments illustrate that the asynchronous variant can be competitive even when a small number of rows is updated per each sample.
APA
Kalantzis, V., Ubaru, S., Wah Wu, C., Kollias, G. & Horesh, L.. (2024). Asynchronous Randomized Trace Estimation. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:4294-4302 Available from https://proceedings.mlr.press/v238/kalantzis24a.html.

Related Material