Gaussian quadrature for matrix inverse forms with applications

Chengtao Li, Suvrit Sra, Stefanie Jegelka
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:1766-1775, 2016.

Abstract

We present a framework for accelerating a spectrum of machine learning algorithms that require computation of \emphbilinear inverse forms u^T A^-1u, where A is a positive definite matrix and u a given vector. Our framework is built on Gauss-type quadrature and easily scales to large, sparse matrices. Further, it allows retrospective computation of lower and upper bounds on u^T A^-1u, which in turn accelerates several algorithms. We prove that these bounds tighten iteratively and converge at a linear (geometric) rate. To our knowledge, ours is the first work to demonstrate these key properties of Gauss-type quadrature, which is a classical and deeply studied topic. We illustrate empirical consequences of our results by using quadrature to accelerate machine learning tasks involving determinantal point processes and submodular optimization, and observe tremendous speedups in several instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-lig16, title = {Gaussian quadrature for matrix inverse forms with applications}, author = {Li, Chengtao and Sra, Suvrit and Jegelka, Stefanie}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {1766--1775}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/lig16.pdf}, url = {https://proceedings.mlr.press/v48/lig16.html}, abstract = {We present a framework for accelerating a spectrum of machine learning algorithms that require computation of \emphbilinear inverse forms u^T A^-1u, where A is a positive definite matrix and u a given vector. Our framework is built on Gauss-type quadrature and easily scales to large, sparse matrices. Further, it allows retrospective computation of lower and upper bounds on u^T A^-1u, which in turn accelerates several algorithms. We prove that these bounds tighten iteratively and converge at a linear (geometric) rate. To our knowledge, ours is the first work to demonstrate these key properties of Gauss-type quadrature, which is a classical and deeply studied topic. We illustrate empirical consequences of our results by using quadrature to accelerate machine learning tasks involving determinantal point processes and submodular optimization, and observe tremendous speedups in several instances.} }
Endnote
%0 Conference Paper %T Gaussian quadrature for matrix inverse forms with applications %A Chengtao Li %A Suvrit Sra %A Stefanie Jegelka %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-lig16 %I PMLR %P 1766--1775 %U https://proceedings.mlr.press/v48/lig16.html %V 48 %X We present a framework for accelerating a spectrum of machine learning algorithms that require computation of \emphbilinear inverse forms u^T A^-1u, where A is a positive definite matrix and u a given vector. Our framework is built on Gauss-type quadrature and easily scales to large, sparse matrices. Further, it allows retrospective computation of lower and upper bounds on u^T A^-1u, which in turn accelerates several algorithms. We prove that these bounds tighten iteratively and converge at a linear (geometric) rate. To our knowledge, ours is the first work to demonstrate these key properties of Gauss-type quadrature, which is a classical and deeply studied topic. We illustrate empirical consequences of our results by using quadrature to accelerate machine learning tasks involving determinantal point processes and submodular optimization, and observe tremendous speedups in several instances.
RIS
TY - CPAPER TI - Gaussian quadrature for matrix inverse forms with applications AU - Chengtao Li AU - Suvrit Sra AU - Stefanie Jegelka BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-lig16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 1766 EP - 1775 L1 - http://proceedings.mlr.press/v48/lig16.pdf UR - https://proceedings.mlr.press/v48/lig16.html AB - We present a framework for accelerating a spectrum of machine learning algorithms that require computation of \emphbilinear inverse forms u^T A^-1u, where A is a positive definite matrix and u a given vector. Our framework is built on Gauss-type quadrature and easily scales to large, sparse matrices. Further, it allows retrospective computation of lower and upper bounds on u^T A^-1u, which in turn accelerates several algorithms. We prove that these bounds tighten iteratively and converge at a linear (geometric) rate. To our knowledge, ours is the first work to demonstrate these key properties of Gauss-type quadrature, which is a classical and deeply studied topic. We illustrate empirical consequences of our results by using quadrature to accelerate machine learning tasks involving determinantal point processes and submodular optimization, and observe tremendous speedups in several instances. ER -
APA
Li, C., Sra, S. & Jegelka, S.. (2016). Gaussian quadrature for matrix inverse forms with applications. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1766-1775 Available from https://proceedings.mlr.press/v48/lig16.html.

Related Material