Nearly Optimal Approximation of Matrix Functions by the Lanczos Method

Summary

The authors investigate the convergence of the Lanczos method for computing $f(A)v$ for a matrix $A$ and a vector $v$. They show a near instance optimality bound that involves the product of the condition numbers of matrices related to $A$ and empirically investigate the bound.

Strengths

The authors investigate the convergence of the Lanczos method for computing matrix functions theoretically and numerically. The results are also meaningful for the machine learning community since matrix functions appear in many machine learning algorithms.

Weaknesses

I think the authors should explain more about how we can interprete the proposed bound. The authors insist the bound captures the convergence behavior of the Lanczos method. The proposed bound involves the condition numbers of the matrices appearing in the denominator of the rational function. I think it is natural, but I couldn't clearly understand why the proposed bound can explain the convergence behavior better than the existing bound in Fact 1, since if the condition numbers of these matrices are large, than the magnitude of $f$ in the bound in Fact 1 can be large, and the factor involving $f$ can also become large.

Questions

- Can you generalize your results to other types of Krylov subspace methods such as rational Krylov methods? - In the middle and the right figures in Figure 1, the relative error seems very small. Did you use higher precision floating point format than double precision?

Rating

6

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors discuss limitations in Section 4.

Summary

A matrix function f(A) for a real, symmetric matrix A and a univariate function f is given as \sum f(\lambda_i) u_i u_i^\top, where \lambda_i are the eigenvalues of A and u_i the corresponding eigenvectors. In practice, one is often interested in matrix-vector products f(A)b for some vector b. In the paper, the approximation quality of the Lanczos-FA method for approximating f(A)b for rational functions f is analyzed theoretically and experimentally. In particular, a known bound that is uniform in the A and b is improved to instance specific bounds using the notion of near instance optimality. The instance specific bounds are not tight. However, they can better explain better the experimentally observed good approximation quality of the Lanczos-FA method that often outperforms more advanced Krylov subspace methods.

Strengths

Originality: The paper provides new theoretical insights into the observed practical behavior of the Lanczos-FA method. It contributes to a better understanding of Krylov subspace methods. The results are non-trivial. Clarity: The paper is well is structured and, in general, easy to read. I did not read the full proof of Theorem 1, but appreciate the proof sketch in Section 2.1. Significance: As far as I can tell, the paper addresses an interesting, practically relevant problem. The paper does not only present upper bounds but also aims to find instances for the Lanczos-FA.

Weaknesses

As far as I can tell, there are no major weaknesses. Minor typos and suggestions for improvement: Introduction: Bayseian Section 1.4: ... functions of interest(ing) ... Footnote 2: Should \|x\|_A be \|b\|_a? Line 148: The (second factor) of the second term ... Figure 2: The axis labels are hardly legible. Figure 5: matvec -> matrix-vector product

Questions

1. I like the proof sketch in Section 2.1, which was easy to follow for a non-expert like me. The only thing that I did not see immediately was the equality below Line 145. It is probably an elementary result, but maybe you can provide a few more insights why this equality holds true. Is well addressed in the author's rebuttal. 2. In the second paragraph of Section 3 (Experiments): Why did you choose the matrices (or the spectra of the matrices) as you did? How do practical spectra look like? What are extreme/challenging spectra? Is also well addressed in the author's rebuttal.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

As far as I can tell, there are no limitations. The bounds are not tight, but I do not consider this a limitation of the paper.

Summary

The submission discusses the optimality (in terms of approximation error) of approximation $(A, b) \rightarrow f(A)b$ with Lanczos' algorithm. The main result (Theorem 1) states that the Lanczos iteration is "near instance optimal". Near-instance-optimality relates to the optimal reconstruction of $r(A)b$ for rational functions $r$. Via the triangle inequality, one can deduce similar statements for general $f$ provided $f$ can be approximated well by rational functions. The submission proves Theorem 1 by repeatedly applying a similar optimality result for $A^{-1} b$ (i.e. $f=1/x$), which is why the final bound comes with scalar $\kappa(A)^q$ where $\kappa$ is the condition number of $A$ and $q$ the order of the denominator of the rational function.

Strengths

The paper provides an interesting perspective on the performance of Lanczos' algorithm for computing matrix functions. The main strength is clarity, partly because the result is relatively strong and partly because the presentation is easy to follow. I appreciate the proof sketch in Section 2.1 and the comparison to prior work in Appendix B (especially in B.2, which I was wondering about while reading the other parts of the manuscript). I also appreciate the code submission. Overall, I think this is a nice paper.

Weaknesses

The paper's main contribution is Theorem 1: near-instance optimality of Lanczos' method for computing $f(A)b$. The weaknesses of this result are twofold: 1. The analysis is limited to exact arithmetic. It is well-known that implementations of Lanczos' method in exact versus finite-precision arithmetic may not match. Focussing on exact arithmetic somewhat limits the practical applicability of Theorem 1. 2. The bound in Theorem 1 includes the constant $\kappa(A)^q$. Similar works (including those discussed in Appendix B) achieve smaller constants, and in practical applications, $\kappa(A)$ can be gigantic. Since the largest $\kappa$ in the experiments seems to be $10^6$ (unless I have missed something), it is slightly unclear whether the bounds actually do explain the superiority of Lanczos' algorithm in practice (where $\kappa$ can exceed $10^6$ by a large margin; see, for instance, the condition number of Gaussian process covariance matrices or discretisations of PDEs). That said, both weaknesses are openly discussed as limitations. Furthermore, Krylov methods have gained popularity in machine learning in recent years, as evidenced by the growing number of papers/submissions on Lanczos, Arnoldi, CG, GMRES, etc. Nevertheless, the submission's connection to existing machine learning literature would be strengthened if at least some of the matrix functions mentioned in the introduction would reappear in the experiments.

Questions

What follows is not directly a question, but the submission's format appears to deviate from the Neurips style in two ways: 1. The abstract contains two paragraphs, even though the template states, "The abstract must be limited to one paragraph." 2. It seems that the mathematics font has been changed from the original Neurips template. I am unsure what Neurips' policy is here. Should these two things be changed?

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are acknowledged. (I discuss this under "Weaknesses" above.)

Summary

The authors study computation of matvecs of a matrix function via the Lanczos method, an in particular try to answer the question of why the basic Lanczos method is competitive or even superior to sophisticated implementations targeting specific matrix functions. They provide theoretical bounds on the error of Lanczos methods for rational functions which they use to produce a bound on generic functions based on distance to the nearest rational, and demonstrate this in numerical experiments.

Strengths

The first major contribution of this article lies in the introduction section, which is establishment of the fact that Lanczos methods outperform sophisticated, problem specific peers in some instances. This "theory-practice gap" in and of itself is an important and consequential fact to establish. The numerical experiments they do to demonstrate this are convincing and well communicated. Subsequently, they offer important theorems governing the ability of Lanczos methods to approximate rational functions, and use this to find a bound based on the l infinity distance between a given function and the nearest rational function of low degree. Numerical experiments demonstrate these results on important practical cases. The way that the main theorem was sketched as special case in Section 2.1 is an exceptional move from a mathematical communication perspective. I was easily able to follow that specific proof, and it gave me intuition as to why the general case might be true without going through the more extensive proof in the appendix. I wish more articles did this, and I will try to do this in my future articles.

Weaknesses

In practice, we care about the effectiveness of this method in floating point arithmetic. But I think it makes sense to partition that off as a separate project, as the contents of the article as it stands are convincing on their own. Here are some grammar issues I noticed (did not affect my scoring): 33) functions repeated. 72) an problem instance -> a problem instance 146) the "and <=" may be missing a term. 147 and 148) May be worth clarifying that it is the right hand side of (6) that is being referred to.

Questions

Congratulations on this paper.

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

The theoretical results rely on the poles of the rational function lying outside of the spectrum of the operator which might not always be the case, but for many practical situations it will be, and the authors' assertion that this case be considered future work is convincing to me.

Summary

The goal of this paper is to better understand the performance of using Lanczos for matrix-function times vector computations. Using Lanczos for this task is the de-facto standard, since it works very well (best vs competitors) in practice. Previous theory is very weak: there is a big gap between the bounds it specifies and the actual performance. The goal of this paper is shrink and where possible eliminate this gap. A stronger bound for Lanczos is established. Extensive experiments are reported.

Strengths

Very well written paper. The main value of the paper is that it takes a well established method and de-facto standard (using Lanczos for matrix-function times vector computations), but with weak theory, and establishes much stronger theory. The reason this is important is that the weak bound motivated researchers to find better algorithms. Such algorithms had better theoretical bounds, but in practice were not as good as Lanczos. This paper closes the gap, giving stronger theory for Lanczos. The experimental evaluation is robust. Appendix also contains additional bounds specific for matrix square root and inverse square root.

Weaknesses

- Bounds are theoretic, and only explain what an existing algorithm achieves. There is no new algorithm in the paper. - The assumption that the poles are outside the gap that contains the eigenvalues seem to imply that the bound works only for a very restricted subset of rational functions. How common is it? - Bounds are only for exact arithmetic. The picture for finite-precision arithmetic can be very different. Even though I can understand why bound for finite-precision arithmetic are outside the scope for this paper, the authors could have conducted experiments with them to see how much the bounds carry to finite-precision. - Even though the problem of computing f(A)b has many ML applications, at the core the paper is focused on the quality of a NLA problem (solving f(A)b). It is more a NLA paper than a ML paper. - In some experiments, in order to show significant gap between the new bound and the old bound (Fact 1), a large number of iteration are used so the error becomes very very small. For example, in Figure 2 (center) the error starts at 10^-5 and goes to 10^-69. In Figure 2 (right) errors start at 10^-10! In applications you will rarely work in these regimes, and will do with much smaller error. It is unclear whether the gap between Fact 1 and the new bound is significant for that regime. - Lemma 1 seems a bit weak: the multiplicative factor or norm(b) is C_r which can be huge. Sure, it is present in (7), but there the minimum it multiplies presumed to be very small. In Lemma 1 it appears on norm(b), which is constant.

Questions

- How hard is it to build rational approximation with poles outside the interval of eigenvalues? Can you give a reference to a general result? - Did you conduct experiments with finite precision to see how much the theory carries over?

Rating

7

Confidence

3

Soundness

4

Presentation

4

Contribution

3

Limitations

Nothing to add.