Paper ID: 811
Title: Gaussian quadrature for matrix inverse forms with applications

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): This paper describes a method to compute bounds on the result of a bilinear inverse form. The bounds are obtained by reformulating the task of interest a Riemman-Stieltjes integral which is then approximated using Gauss-type quadratures.  The advantage of such approach is that one automatically obtains a series of upper and lower bounds for the result.  These bounds are obtained before finding the exact solution to the problem and can hence be used to speed-up other algorithms that rely on computing bilinear inverse forms. Examples of these include approximate inference with determinantal point process and submodular maximization. 

Clarity - Justification: The paper is very clearly written and it is easy to follow. 

Significance - Justification:  The paper gives some theoretical results involving the computation of bounds on bilinear inverse forms that very often arise in machine learning problems. I believe the paper is hence of great interest for the machine learning community.  The experiments also seem convincing.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Some abbreviations are against the writing guidelines of ICML papers. Examples, are Fig. or Sec.

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): gaussian quadrature is proposed for estimating quadratic bilinear forms,some bounds are provided on the estimates and a range of examples are provided in illustrating the estimator

Clarity - Justification: The clarity of the paper was fine and the ideas were accessible with not too much effort. However it was unclear how this proposed approach lies in relation to other methods for estimating inverse bilinear forms - something that seemed to have bypassed the authors.

Significance - Justification: It is difficult to assess the significance of the paper as written primarily due to the focus of providing many illustrative applications - but missing the other work in the literature on this problem thus making it difficult to assess its significance.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The focus is on gauss quadrature approaches to the problem. There are however other approaches e.g. extrapolation of the matrix moments and interpolation (Brzezinski, 99) and recent work of P Fika and co-workers. It is a shame that these are given no mention in this manuscript as it is difficult to assess the significance of the contribution as it is currently presented. Its a nice contribution so although I'm weakly rejecting it could be weakly accepted if the authors acknowledged and considered the alternative approaches the literature

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.):        This paper presents a framework of computing the bilinear inverse forms u^TA^{-1}u, which have been found in a wide range of places in machine learning. More precisely, this paper considers the bilinear inverse forms as an integral and utilizes the Gauss types of quadrature rules to approximate the integral. This method comes from the beautiful connections among orthogonal polynomials, tridiagonal matrices and Lanczos algorithms. The main theoretical contribution is the iterative bounds and convergence rate analysis on Gauss, Gauss-Radau and Gauss-Lobatto rules. Furthermore, the author demonstrates the usefulness of their results with two ML applications, sampling from determinantal point processes (DPP) and accelerating a greedy algorithm for submodular optimization.        

Clarity - Justification:  This is paper is beautifully written with the contributions clearly stated. I enjoyed reading this paper. The empirical results are clearly illustrated and the experimental setting is clear.        

Significance - Justification:          Computing bilinear form with matrix inversion is obviously a very important problem in machine learning. The usages of the bounds of the quadrature rule on DPP and submodular optimization look novel to me. However, the contribution of the theoretical results for the Gauss-type quadrature is hard for me to evaluate.        

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.):                  Line 235: but in this case, you'll need to run Lanczos twice, isn't it?         Line 299: "the" is written twice.         Line 294: About the reference (Schwartz, 1966), or is this the correct one: H. S. Wilf, Mathematics for the physical sciences, 1962?          Line 335: One could also just run the Lanczos for $N$ steps and get the Jacobi matrix $J$ and then calculating e_1^TJ^{-1}e_1 is a computational cheap process given that $J$ is tridiagonal. I'm curious to see how this compares to Algorithm 1 in terms of performance.          Line 377: It is known that the convergence of the Gauss quadrature rule depends on how fast the Ritz values converge to the eigenvalues of A, which is not trivial to analyze. I'm wondering how you tackle this?        

=====