Asynchronous Randomized Trace Estimation
Vasileios Kalantzis, Shashanka Ubaru, Chai Wah Wu, Georgios Kollias, Lior Horesh
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.
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.}
}