Gauss quadrature for matrix inverse forms with applications
This work provides a scalable solution for accelerating algorithms in machine learning that rely on matrix inverse computations, though it is incremental as it builds on classical Gauss quadrature methods.
The paper tackles the problem of efficiently computing bilinear inverse forms u^T A^{-1} u for large, sparse matrices in machine learning, achieving linear convergence rates and significant speedups in applications like determinantal point processes and submodular optimization.
We present a framework for accelerating a spectrum of machine learning algorithms that require computation of bilinear inverse forms $u^\top A^{-1}u$, 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^\top A^{-1}u$, 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.