Nearly Optimal Approximation of Matrix Functions by the Lanczos Method

Authors: noah  amsel
tyler  chen
anne  greenbaum
cameron  musco
christopher  musco
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-12 20:12:48

Abstract: Approximating the action of a matrix function $f(\vec{A})$ on a vector $\vec{b}$ is an increasingly important primitive in machine learning, data science, and statistics, with applications such as sampling high dimensional Gaussians, Gaussian process regression and Bayesian inference, principle component analysis, and approximating Hessian spectral densities.
Over the past decade, a number of algorithms enjoying strong theoretical guarantees have been proposed for this task.
Many of the most successful belong to a family of algorithms called Krylov subspace methods.
Remarkably, a classic Krylov subspace method, called the Lanczos method for matrix functions (Lanczos-FA), frequently outperforms newer methods in practice. Our main result is a theoretical justification for this finding: we show that, for a natural class of rational functions, Lanczos-FA matches the error of the best possible Krylov subspace method up to a multiplicative approximation factor. 
The approximation factor depends on the degree of $f(x)$'s denominator and the condition number of $\vec{A}$, but not on the number of iterations $k$. Our result provides a strong justification for the excellent performance of Lanczos-FA, especially on functions that are well approximated by rationals, such as the matrix square root.

Main paper: 
 introduction: 
 Given a symmetric matrix A ∈ R 𝑑×𝑑 with eigendecomposition A = 𝑑 𝑖=1 𝜆 𝑖 u 𝑖 u T 𝑖 , the matrix function 𝑓 (A) corresponding to a scalar function 𝑓 : R → R is defined asEQUATIONMatrix functions arise throughout machine learning, data science, and statistics. For instance, the matrix square root is used in sampling Gaussians, Bayesian modeling, and Gaussian processes [4, 5, 59] , general fractional matrix powers are used in Markov chain modeling and Rényi entropy estimation [68, 42, 43, 19] , the matrix logarithm is used for determinantal point processes, kernel learning, and approximating log-determinants for Gaussian process regression and Bayesian inference [17, 39, 31] , the matrix sign is used in principal components regression and spectral density estimation [29, 18, 44, 58, 32, 69, 13, 7, 14] , and the matrix exponential is used in network science [3, 67, 48] . In many of these applications, we do not need to compute the matrix 𝑓 (A) itself, but rather its action on a vector b ∈ R 𝑑 ; i.e., 𝑓 (A)b. This task can be performed much more efficiently than computing an eigendecomposition of A and forming 𝑓 (A) using (1) .Perhaps the first general purpose method for approximating 𝑓 (A)b is the Lanczos method for matrix function approximation (Lanczos-FA) [22, 30] , which is the focus of the present paper. Over the past decade, a number of special purpose algorithms, designed for a single function or class of functions, have been developed [23, 16, 26, 44, 11] . These newer algorithms often satisfy strong theoretical guarantees better than the best-known bounds for Lanczos-FA. The present paper is motivated by the following remarkable observation:Despite being arguably the simplest and most general algorithm for computing 𝑓 (A)b, Lanczos-FA frequently outperforms special purpose algorithms, sometimes by orders of magnitude, on common test problems.For instance, in Figures 4, 5 , and 8 we compare Lanczos-FA with specialized algorithms [44, 59, 11] that satisfy the best-known theoretical guarantees for computing 𝑓 (A)b for the particular functions they were designed for. In these experiments Lanczos-FA drastically outperforms these methods, despite the fact that it was not designed for any particular function. Because of its outstanding performance, Lanczos-FA is perhaps the most commonly used algorithm for computing 𝑓 (A)b in practice. The main goal of this paper is to improve our theoretical understanding of why Lanczos-FA performs so well, in order to help close the theory-practice gap.Lanczos-FA falls into a class of algorithms called Krylov Subspace Methods (KSMs). KSMs are among the most powerful and widely used algorithms for a broad range of computational tasks including solving linear systems, computing eigenvalues/vectors, and low-rank approximation [62, 38, 47, 65] . Like other KSMs for computing 𝑓 (A)b, Lanczos-FA iteratively constructs an approximation from the Krylov subspace K 𝑘 (A, b) := span{b, Ab, . . . , A 𝑘-1 b}.(EQUATIONThe Lanczos algorithm [46] produces an orthonormal basis Q = [q 1 , . . . , q 𝑘 ] for the Krylov subspace K 𝑘 (A, b) and a symmetric tridiagonal matrix T satisfying T = Q T AQ [62] . The Lanczos-FA algorithm uses this Q and T to approximate 𝑓 (A)b. Definition 1. The Lanczos-FA iterate for a problem instance ( 𝑓 , A, b, 𝑘) is defined aslan 𝑘 ( 𝑓 ; A, b) := Q 𝑓 (T)Q T b,where Q and T are as above.In our analysis we assume exact arithmetic. We do not discuss the implementation of Lanczos or Lanczos-FA since there are many resources on this topic; see for instance [52, 8, 9] . Fortunately, if the Lanczos algorithm is implemented properly, its finite-precision behavior closely follows its exact-arithmetic behavior on a nearby problem [33] . See Section 5 for further discussion.For a wide variety of problem instances, Lanczos-FA is observed to converge almost as quickly as the best approximation to 𝑓 (A)b that could be returned by any KSM run for the same number of iterations. In particular, all KSMs output approximations that lie in the span of K 𝑘 (A, b), that is, approximations of the form 𝑝(A)b for a polynomial 𝑝 of degree less than 𝑘. Given a problem instance ( 𝑓 , A, b, 𝑘), the best possible approximation returned by a Krylov method is 4opt 𝑘 ( 𝑓 ; A, b) := argminx∈ K 𝑘 (A,b) ∥ 𝑓 (A)b -x∥ 2 .By definition, the error of this Krylov optimal iterate can be characterized as follows:EQUATIONFor general matrix functions, no efficient algorithm for computing opt 𝑘 ( 𝑓 ; A, b) is known, but as shown in Figure 1 , the solution returned by Lanczos-FA often nearly matches the error of this best approximation. It is thus natural to ask if, at least for some class of problems, Lanczos-FA satisfies the following strong notion of approximate optimality: "Instance Optimal" is the right hand side of Definition 2 with 𝐶 = 𝑐 = 1, which is a lower bound for all KSMs, including Lanczos-FA. Lanczos-FA performs nearly instance optimally on a wide range of problems, far better than Fact 3 predicts. This is easily seen in the bottom plots, which show the ratio of the error of the Lanczos-FA iterate and the Krylov optimal iterate, opt 𝑘 ( 𝑓 ; A, b).Definition 2 (Near Instance Optimality). For a problem instance ( 𝑓 , A, b, 𝑘), we say that a Krylov method is nearly instance optimal with parameters 𝐶 and 𝑐 if∥ 𝑓 (A)b -alg 𝑘 ( 𝑓 ; A, b) ∥ 2 ≤ 𝐶 min deg( 𝑝) <𝑐𝑘 ∥ 𝑓 (A)b -𝑝(A)b∥ 2 .Above, alg 𝑘 ( 𝑓 ; A, b) denotes the output of an algorithm (e.g., Lanczos-FA) obtained from the Krylov subspace K 𝑘 (A, b), i.e., the output after 𝑘 iterations.In Definition 2, 𝐶 ≥ 1 and 𝑐 ≤ 1 allow some slack in comparing to the Krylov optimal iterate. The right hand side depends on the entire problem instance, ( 𝑓 ; A, b), which is why we call the guarantee "instance optimal".The best bound for Lanczos-FA applying to a broad class of functions is the following common bound for Lanczos-FA; see for instance [61, 54, 52, 10] . Fact 3. For all problem instances ( 𝑓 , A, b, 𝑘), Lanczos-FA satisfies∥ 𝑓 (A)b -alg 𝑘 ( 𝑓 ; A, b) ∥ 2 ≤ 2∥b∥ 2 min deg( 𝑝) <𝑘 max 𝑥 ∈ [𝜆 min ,𝜆 max ] | 𝑓 (𝑥) -𝑝(𝑥)| .Fact 3 is in some sense an optimality guarantee; it compares the convergence of Lanczos-FA to the best possible uniform polynomial approximation to 𝑓 (𝑥). However, it does not take into account properties of A such as isolated or clustered eigenvalues, and as seen in Figure 1 , it typically only gives a loose upper bound on the performance of Lanczos-FA.To date, near-instance-optimality guarantees for Lanczos-FA akin to those of Definition 2 are known only in a few special cases. The most well-known is when 𝑓 (𝑥) = 1/𝑥 and A is positive definite, in which case Lanczos-FA is mathematically equivalent to the celebrated Conjugate Gradient algorithm, and therefore exactly optimal in the A-norm [47] . The instance-optimality guarantee for Lanczos-FA in this setting is used to prove well-known super-exponential convergence in certain settings [6, 47, 8] . In contrast, a bound like Fact 3 only provides exponential convergence and is widely understood by the numerical linear algebra community to not accurately describe the actual behavior of the algorithm in most cases [35, 47, 8] . The only other near-optimality guarantees for Lanczos-FA of which we are aware concern A -1 b for nonsymmetric A [12] and the matrix exponential exp(-𝑡A)b [20] . In both cases, Lanczos-FA satisfies guarantees that are reminiscent of (although weaker than) Definition 2. Further discussion is given in Appendix B.1.We also remark that there are a number of works which aim to relate the convergence of of Lanczos-FA for functions with certain integral representations to the convergence of conjugate gradient on linear systems [41, 24, 27, 28, 25, 10] . While these analyses provides spectrum dependent convergence guarantees, they are weaker than Definition 2 because it is not clear how the best possible KSM approximation to a given function relates to the convergence of conjugate gradient. These bounds were mostly developed for use as a posteriori stopping criteria rather than as a theoretical explication for the behavior of Lanczos-FA.In Section 2, we prove near instance optimality for a broad class of rational functions (Theorem 4).To the best of our knowledge, this is the first true instance-optimality guarantee for Lanczos-FA to be proven for any function besides 𝑓 (𝑥) = 1/𝑥. In Section 2.2, we discuss how results of this kind imply related guarantees for functions that are uniformly well-approximated by rationals, which includes many functions of interest in machine learning. In Section 3, we additionally show that Lanczos-FA satisfies a weaker version of near optimality for two crucial non-rational matrix functions-the square root and inverse square root (Theorems 6 and 7). Appendix C compares the this version of optimality to Definition 2 (near instance optimality) and to that of Fact 3. In Section 4, we present experimental evidence showing that, for many natural problem instances, our bounds are significantly sharper than the standard bound of Fact 3. These experiments also demonstrate that despite its generality, Lanczos-FA often converges significantly faster than other methods in practice.We conclude with a discussion of next steps and open problems in Section 5.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: Our abstract refers to the main theoretical result, Theorem 4, and to the experimental results of Section 4, particularly Figure 2 .Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
near optimality for rational functions: 
 In this section, we study the Lanczos-FA approximation to 𝑟 (A)b, where 𝑟 (𝑥) is a rational function with real-valued poles that lie in R \ I, whereEQUATIONwhere 𝑛(𝑥) is any degree 𝑝 polynomial and𝑚(𝑥) = (𝑥 -𝑧 1 ) (𝑥 -𝑧 2 ) • • • (𝑥 -𝑧 𝑞 ), 𝑧 𝑖 ∈ R \ I.Since 𝑧 𝑗 ∉ I, ±(A -𝑧 𝑗 I) is either positive definite or negative definite. For convenience, we defineEQUATIONOur main result on rational functions is the following near-instance-optimality bound, which holds under a mild assumption on the number of iterations 𝑘: Theorem 4. Let 𝑟 (𝑥) = 𝑛(𝑥)/𝑚(𝑥) be a degree ( 𝑝, 𝑞)-rational function as in (4) and define A 𝑗 as in (5) . Then, if 𝑘 > max{𝑝, 𝑞 -1}, the Lanczos-FA iterate satisfies the bound∥𝑟 (A)b -lan 𝑘 (𝑟; A, b) ∥ 2 ≤ 𝑞 • 𝜅(A 1 ) • 𝜅(A 2 ) • • • 𝜅(A 𝑞 ) min deg( 𝑝) <𝑘-𝑞+1 ∥𝑟 (A)b -𝑝(A)b∥ 2 .We prove this theorem in Appendix A. Above, 𝜅(A 𝑖 ) is the condition number of A 𝑖 , the ratio of the largest to smallest magnitude eigenvalues of A 𝑖 . Theorem 4 shows that Lanczos-FA used to approximate 𝑟 (A)b satisfies near instance optimality, as in Definition 2, with𝐶 = 𝑞 • 𝜅(A 1 ) • 𝜅(A 2 ) • • • 𝜅(A 𝑞 ), 𝑐 = 1 -(𝑞 -1)/𝑘.In particular, when A is positive definite and each of the 𝑧 𝑖 are negative (as is the case for rational function approximations of many functions including the square root [37] ), then 𝐶 ≤ 𝑞𝜅(A) 𝑞 .As discussed in Section 5, we expect that Theorem 4 can be tightened by significantly reducing the prefactor. Nevertheless, as illustrated in Figure 2 , even in its current form, the bound improves on the standard bound of Fact 3 in many natural cases; i.e., it more tightly characterizes the observed convergence of Lanczos-FA. Finally, as discussed further in Section 2.2, we note that, beyond rational functions being an interesting function class in their own right, Theorem 4 has implications for understanding the convergence of Lanczos-FA for functions like the square root which are much easier to approximate with rational functions than polynomials.Figure 2 : Despite its large prefactor, the bound of Theorem 4 qualitatively captures the convergence behavior of Lanczos-FA for rational functions. It can be tighter than the standard bound of Fact 3, even for a moderate number of iterations 𝑘. We use rational approximations to exp(-𝑥/10) and log(𝑥) for comparison with Figure 1 ; see Section 4 for more details.Our proof of Theorem 4 leverages the near optimality of Lanczos-FA in computing A -1 b to obtain a bound for general rational functions. For illustration, consider the simplest possible rational function for which we are unaware of any previous near-optimality bounds: A -2 b when A is positive definite. The Lanczos-FA approximation for this function isQT -2 Q T b = QT -1 Q T QT -1 Q T b.Using the triangle inequality and submultiplicativity, we can bound the error of the approximation asEQUATION)Using the normal equations and the fact that Q is a basis of the Krylov subspace, it is possible to show that QT -1 5 projector onto Krylov subspace. HenceQ T A = Q(Q T AQ) -1 Q T A is the A-norm∥A -2 b -QT -1 Q T AA -2 b∥ A = min x∈ K 𝑘 (A,b) ∥A -2 b -x∥ A := min deg( 𝑝) <𝑘 ∥A -2 b -𝑝(A)b∥ A .Therefore, using ∥x∥ 2 ≤ (1/ √ 𝜆 min ) ∥x∥ A and ∥x∥ A ≤ √ 𝜆 max ∥x∥ 2 , the first term on the right hand side of (6) can be bounded as∥A -2 b -QT -1 Q T AA -2 b∥ 2 ≤ √︁ 𝜅(A) min deg( 𝑝) <𝑘 ∥A -2 b -𝑝(A)b∥ 2 .Similarly, the second factor of the second term on the right hand side of (6) can be bounded as∥A -1 b -QT -1 Q T AA -1 b∥ 2 ≤ √︁ 𝜅(A) min deg( 𝑝) <𝑘 ∥A -1 b -𝑝(A)b∥ 2 .Then, since 𝑥 𝑝(𝑥) is polynomial of one degree larger than 𝑝(𝑥),min deg( 𝑝) <𝑘 ∥A -1 b -𝑝(A)b∥ 2 ≤ min deg( 𝑝) <𝑘-1 ∥AA -2 b -A𝑝(A)b∥ 2 ≤ 𝜆 max min deg( 𝑝) <𝑘-1 ∥A -2 b -𝑝(A)b∥ 2 .Plugging the above bounds into (6) and using the fact that the eigenvalues of T are contained in[𝜆 min , 𝜆 max ] so that ∥QT -1 Q T ∥ 2 ≤ ∥T -1 ∥ 2 ≤ 1/𝜆 min , ∥A -2 b -lan 𝑘 (𝑥 -2 ; A, b) ∥ 2 ≤ 2𝜅(A) 3/2 min deg( 𝑝) <𝑘-1 ∥A -2 b -𝑝(A)b∥ 2 .Bounding 𝜅(A) 3/2 by 𝜅(A) 2 gives the bound in Theorem 4.Our proof of Theorem 4 generalizes the above approach. We write the Lanczos-FA error for approximating 𝑟 (A)b in terms of the error of the optimal approximations to a set of simpler rational functions, and then reduce polynomial approximation of 𝑟 (𝑥) to polynomial approximation of each of these particular functions.Theorem 4 can be used to derive guarantees for other (non-rational) functions. In particular, consider any function 𝑓 (𝑥) that is uniformly well approximated by a low-degree rational function 𝑟 (𝑥) on I = [𝜆 min , 𝜆 max ], the interval containing all of the eigenvalues of A; i.e., suppose ∥𝑟 -𝑓 ∥ I := max 𝑥 ∈ I |𝑟 (𝑥)-𝑓 (𝑥)| is small. A natural way to approximate 𝑓 (A)b, used in [4, 5, 59] , is to construct 𝑟 (𝑥) and output 𝑟 (A)b, using some iterative linear solver to quickly apply the denominators of the partial fraction decomposition of 𝑟 (𝑥). Alternatively, if we have an instance-optimality guarantee for Lanczos-FA on rational functions like Theorem 4, we could use Lanczos-FA to compute 𝑟 (A)b.The following analysis shows that simply using Lanczos-FA on 𝑓 (𝑥) itself cannot be much worse. Lemma 5. Assume the we have the following instance-optimality guarantee for rational functions:EQUATIONHere, 𝐶 𝑟 and 𝑐 𝑟 depend on the choice of approximant 𝑟 (𝑥). Then the error of Lanczos-FA on 𝑓 (𝑥) is bounded as follows:EQUATIONWe prove this lemma, which follows directly from the triangle inequality, in Appendix A.5. Compare the form of this bound to that of Definitions 2 and 13. It is close to a near-instance-optimality guarantee, except for the first term, which requires 𝑓 (𝑥) to be uniformly well-approximated by a rational function 𝑟 (𝑥) on [𝜆 min , 𝜆 max ]. This is still much stronger than Fact 3, which requires 𝑓 (𝑥) to be uniformly well-approximated by a polynomial to guarantee that Lanczos-FA provides a good approximation. There are many functions with lower degree rational approximations than polynomial approximations, even when we require the rational function 𝑟 (𝑥) to have poles only in R \ I (as in our Theorem 4). Such rational approximations are obtainable by the Remez algorithm [64, Chapter 24] , and for many important functions they are also known explicitly. For example, a uniform polynomial approximation to the square root on a strictly positive interval [𝜆 min , 𝜆 max ] requires degree Ω( √︁ 𝜆 max /𝜆 min ) [64, Chapter 8] . On the other hand, a uniform rational approximation can be obtained with degree only 𝑂 (log(𝜆 max /𝜆 min )) [37, 64, Chapter 25] . Likewise, a uniform polynomial approximation to exp(-𝑥) on the interval [0, 𝐵] requires degree Ω( √ 𝐵) [1] , but uniform rational approximations can be constructed with no dependence on 𝐵 [63] . For such functions, we expect (8) to be stronger than Fact 3.Notice also that, while in Lemma 5, we assume 𝑓 (𝑥) is well-approximated by a rational function, we are not required to actually construct the approximation. Indeed, since it holds for any 𝑟 (𝑥), instead of fixing a rational approximation of a certain degree, (8) automatically balances ∥𝑟 -𝑓 ∥ I , which decreases as the degree grows, with 𝐶 𝑟 , which may increase as the degree grows (see Figure 4 ). In the previous section, we proved that Lanczos-FA is nearly instance optimal for rational functions in the sense of Definition 2. In this section, we prove that Lanczos-FA satisfies a weaker form of near optimality for two important non-rational functions: square root and inverse square root. We term this weaker form of guarantee "near spectrum optimality". In Appendix C, we formally define this notion and compare it to Definition 2. We first state our bound for the inverse square root. Theorem 6. Let Λ be the spectrum of A. Then for 𝑘 ≥ 2, the Lanczos-FA iterate satisfies the bound∥A -1/2 b -lan 𝑘 (𝑥 -1/2 ; A, b) ∥ 2 ≤ 3 √ 𝜋𝑘 𝜅(A) ∥b∥ 2 min deg( 𝑝) <𝑘/2 max 𝑥 ∈Λ 1 √ 𝑥 -𝑝(𝑥) .That is, Lanczos-FA applied to the inverse square root satisfies Definition 12 ("near spectrum optimality") withEQUATION.We prove this theorem in Appendix D. The proof relies on comparing the error of the 𝑘th Lanczos iterate for 𝑥 -1/2 to that of the Lanczos iterate for 𝑥 -1 . First, applying a bound from [10] , we use the Cauchy integral formula to upper bound the error of Lanczos-FA on 𝑥 ±1/2 by its error on 𝑥 -1 (Lemma 16). Second, as Equation ( 17) shows, Lanczos-FA is nearly instance optimal for the function 𝑥 -1 ; that is, it outputs 𝑝(A)b where 𝑝 is (nearly) the degree 𝑘 polynomial that best approximates 𝑥 -1 . Third, the best degree 𝑘 polynomial approximation to 𝑥 -1 must have lower error than the best degree 𝑘/2 approximation to 𝑥 -1/2 . This is because any degree 𝑘/2 approximation to 𝑥 -1/2 can be squared to yield a good degree 𝑘 polynomial approximation to 𝑥 -1 . Combining these three steps upper bounds the error of the 𝑘th Lanczos-FA iterate for 𝑥 -1/2 by the error of the best degree 𝑘/2 polynomial approximation of 𝑥 -1/2 .Nearly the same argument can be used to prove spectrum optimality of Lanczos-FA for the functionA -1/𝑛 b for any 𝑛 ∈ N with 𝐶 = (2 𝑛 -1) • 𝜅(A)/ √ 𝜋𝑘.Furthermore, using Lemma 15 of Appendix C, we can convert Theorem 6 into a near-instance-optimality guarantee at the price of strong dependence of 𝐶 on b. We next state our optimality result for the matrix square root. Theorem 7. Let Λ be the spectrum of A. Then for 𝑘 ≥ 2, the Lanczos-FA iterate satisfies the bound∥A 1/2 b -lan 𝑘 (𝑥 1/2 ; A, b) ∥ ≤ 3𝜅(A) 2 𝑘 3/2 ∥b∥ 2 min deg( 𝑝) <𝑘/2+1 max 𝑥 ∈Λ∪{0} √ 𝑥 -𝑝(𝑥) .This bound resembles Definition 12 withEQUATION.However, it is slightly weaker in that the maximization is taken over Λ ∪ {0} instead of only Λ.The proof of Theorem 7 is nearly the same as that of Theorem 6, and it likewise appears in Appendix D. Ideally, if 𝑝 is a polynomial approximation to 𝑥 1/2 , we would like to claim that ( 𝑝(𝑥)/𝑥) 2 yields a good polynomial approximation to 𝑥 -1 . However, since this function is not necessarily a polynomial, we must instead use use𝑝 ( 𝑥 ) -𝑝 (0) 𝑥 2, which introduces the need to include {0} in the maximization on the right-hand side.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Each of our theorems clearly states all assumptions. Section 5 discusses the limitations of our current results and the open questions that remain.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]Justification: Formal theorem statements include all assumptions. All proofs appear in Appendices A, C, and D.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments: 
 We now present several numerical experiments to assess the quality of our instance-optimality bounds, Theorem 4 and Lemma 5. Our results show that, despite the large prefactor 𝐶, our bounds already supersede the standard uniform approximation bound (Fact 3) in many cases. We also compare Lanczos-FA against several recently proposed algorithms for computing matrix functions with strong theoretical guarantees. We find that, in practice, Lanczos-FA performs better than all of them. We implement Lanczos-FA in high precision arithmetic using the flamp library, which is based on mpmath [51] , in order to mitigate any potential impacts of finite precision arithmetic and observe the convergence behavior of the algorithm beyond the standard machine precision. 6In Figure 1 , we compare the performance of Lanczos to the instance-optimal KSM (which we can compute by direct methods) and against Fact 3 for various matrix functions and spectra. We use three test matrices A ∈ R 100×100 which all have condition number 100. The first has a uniformly-spaced spectrum, the second has a geometrically-spaced spectrum, and the third has eigenvalues that are all uniformly-spaced in a narrow interval except for ten very small eigenvalues. We compute the bound from Fact 3 using the Remez algorithm and compute the instance-optimal approximation using least squares regression onto the Krylov basis Q. In Figure 1 , as in almost all cases we tried, Lanczos-FA The maximum observed ratio between the error of Lanczos-FA and the optimal error over choices of b when approximating A -𝑞 for matrices with varying condition number 𝜅. Each point corresponds to a pair (𝜅, 𝑞). Points with the same color have the same value of 𝜅. On the left, the dotted line plots √ 𝑞𝜅 for the maximum 𝜅 considered (10 6 ). On the right, the dotted line plots √ 𝑞𝜅 for the maximum 𝑞 considered (2 6 ). Overall, the optimality ratio appears to scale at least as Ω( √ 𝑞𝜅).performs nearly as well as the instance-optimal approximation. For instance, the error is never more than a small multiple of the optimal error in the experiments we did.To better understand Theorem 4, we compare the bound to the true convergence curve of Lanczos-FA for various rational functions in Figure 2 . We also plot Fact 3 for reference. We use the same matrices and b vectors as in Figure 1 ; results are similar if b is instead chosen as a uniform linear combination of A's eigenvectors. We choose rational functions to match the functions used for Figure 1 . We construct a degree 5 rational approximation to exp(-𝑥/10) following [63] . We construct a degree 10 approximation to log(𝑥) using the BRASIL algorithm [40] and verify that it has real poles outside the interval of the eigenvalues. Despite Theorem 4's exponential dependence on the degree of the rational function being applied, Figure 2 shows that it matches the shape of the convergence curve well and is tighter than Fact 3 when the number of iterations is large. That said, in all cases plotted, Lanczos-FA always returns an approximation much closer to optimal than predicted by Theorem 4, suggesting that the leading coefficient in our bound is pessimistic.Theorem 4 upper bounds the optimality ratio by𝐶 = 𝑞 • 𝜅(A 1 ) • 𝜅(A 2 ) • • • 𝜅(A 𝑞 ).We conjecture that this bound is far from tight. However, the following experiment provides evidence that it is not possible to entirely eliminate the dependence on the rational function's denominator degree 𝑞.In particular, for parameters (𝜅, 𝑞), consider approximating A -𝑞 b where A has spectrum 𝜆 1 = 1 and 𝜆 2 , . . . , 𝜆 100 evenly spaced between 0.999995 • 𝜅 and 𝜅. In this case,𝜅(A 1 ) = • • • = 𝜅(A 𝑞 ) = 𝜅(A) = 𝜅.We generate a grid of problems by picking different combinations of (𝜅, 𝑞) and tuning b in a limited way to maximize the maximum ratio between the error of Lanczos-FA and the optimal Krylov error over all iterations. In particular, we took b to be an all ones vector, except we varied its first entry, using grid search to maximize the optimality ratio. The results, plotted in Figure 3 , suggest that the optimality ratio grows at least as Ω(√︁ 𝑞 • 𝜅(A)).We have yet to find harder problem instances than this.As noted in Section 2.2, an instance-optimality guarantee for rational functions also implies that Lanczos-FA performs well on functions that are well-approximated by rationals. As an example, we consider the function 𝑓 (𝑥) = 𝑥 -0.4 , for which a rational approximation in any degree can be found using the BRASIL algorithm [40] . Figure 4 shows how applying Lanczos-FA to these rational approximations compares to applying Lanczos-FA directly to the 𝑓 (𝑥) itself to approximate A -0.4 b. When the number of iterations is small, both methods perform nearly optimally, as the accuracy is limited more by the small size of the Krylov subspace than by the difference between 𝑓 (𝑥) and the rational approximant (that is, the second term in (8) dominates the first term). As the number of iterations grows, the error due to approximating 𝑓 (𝑥) in the Krylov subspace continues to decrease while the error of uniformly approximating 𝑓 (𝑥) by some fixed rational function remains fixed (that is, the first term in (8) dominates the first term); however, increasing the degree of the Figure 4 : Applying Lanczos-FA to the function A -0.4 and rational approximations of various degrees found using the BRASIL algorithm [40] . In this experiment, the spectrum of A contains two clusters: 10 eigenvalues uniformly spaced near 1, and 90 eigenvalues uniformly spaced near 100.As predicted by the bound in Section 2.2, convergence of Lanczos-FA for this function appears to closely track that of a high degree rational approximant.Figure 5 : A comparison of Lanczos-FA with two methods from [44] ("rational" and "slanczos") for computing the matrix sign function, which work by using a stochastic iterative method to approximate rational approximations to the step function of various degrees. The "rational" method is the main one studied in [44] , while "slanczos" is included because it is the best performing in their experiments. Each panel corresponds to one of the test problems from [44] . Iterations of these methods are counted in number of inner products with rows of A rather than number of matrix-vector products with A as a whole. To compare these with Lanczos-FA, we consider 𝑑 such inner products to be equivalent to one matrix-vector product.rational approximant decreases this source of error. This shows that understanding the convergence of Lanczos-FA for the entire family of rational approximations goes a long way toward explaining its convergence for non-rational functions. In the limit, Lanczos-FA applied to 𝑓 (𝑥) itself appears to automatically inherit the instance optimality of a suitably high-degree rational approximation.This result has an additional implication. A number of papers use explicit rational approximations to compute non-rational matrix functions [4, 5, 36, 59 ]. These approximations are often applied by applying conjugate gradient (or a related method) to each of the terms in the sum [36, 59] . In the case conjugate gradient is used, the resulting algorithm is mathematically identical to Lanczos-FA used to compute the the rational approximation. However, Figure 4 suggests that simply using Lanczos-FA on the original function is both simpler and converges faster (though memory usage and other factors may need to be considered).Another line of work uses specialized iterative methods that exploit problem structure to apply the rational approximations [29, 2, 53, 44] . In Figure 5 , we compare Lanczos-FA to two such methods from [44] for computing sign(A), for A of the form A = B T B -𝜆I. While they achieve better theoretical bounds than are known for Lanczos-FA, Lanczos-FA far outperforms them on the test problems used in [44] .Figure 6 : Convergence of Lanczos-FA for rational functions with poles in A's eigenvalue range or that are imaginary. The optimality ratio can be very large for some iterations. Similar behavior is seen for functions like sign(A) that have a discontinuity in the interval of A's eigenvalues. However, the "overall" convergence of Lanczos-FA still appears to closely track the instance-optimal solution.Additional Experiments. In Section 3 we introduce bounds for the matrix square root and inverse square root, and in Appendix E.1 we provide numerical tests to study the sharpness of the bounds, verifying that they can improve on Fact 3. In Appendix E.2, we demonstrate the convergence behavior of Lanczos-FA on rational functions with poles inside the range of eigenvalues (Figure 6 ). This illustrates why a bound like Theorem 4 is not possible, but suggests a weaker bound, such as the bound in [12] for 𝑓 (𝑥) = 1/𝑥 and indefinite A, may be possible. Appendix E.3 shows that, unlike Lanczos-FA, a related algorithm called Lanczos-OR [11] (which is exactly optimal for rational functions, though not in the Euclidean norm) can perform poorly on high degree rational functions when the error is measured in the Euclidean norm.The following lemma allows us to relate the optimality of the functions 𝑟 𝑗 as measured in the A 𝑗norm to that of 𝑟 𝑞 = 𝑟 as measured in the 2-norm. Lemma 11. For any 𝑘 > 𝑞 -𝑗,∥𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) ∥ ≤ 𝜅(A 𝑗 ) 1/2 • ∥𝑚 𝑗+1,𝑞 (A) ∥ 2 min deg( 𝑝) <𝑘-(𝑞-𝑗 ) ∥𝑟 (A)b -𝑝(A)b∥ 2 .Proof. Recall that opt 𝑘 (𝑟 𝑗 , A 𝑗 ) is the optimal approximation to 𝑟 𝑗 (A)b in the A 𝑗 -norm, so can be related to the optimal approximation in the 2-norm.∥𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) ∥ 2 = A -1/2 𝑗 A 1/2 𝑗 (𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 )) 2 ≤ ∥A -1/2 𝑗 ∥ 2 • ∥𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) ∥ A 𝑗 = ∥A -1 𝑗 ∥ 1/2 2 min deg( 𝑝) <𝑘 ∥𝑟 𝑗 (A)b -𝑝(A)b∥ A 𝑗 ≤ ∥A -1 𝑗 ∥ 1/2 2 • ∥A 𝑗 ∥ 1/2 2 min deg( 𝑝) <𝑘 ∥𝑟 𝑗 (A)b -𝑝(A)b∥ 2 = 𝜅(A 𝑗 ) 1/2 min deg( 𝑝) <𝑘 ∥𝑟 𝑗 (A)b -𝑝(A)b∥ 2 .We now relate the error of approximating 𝑟 𝑗 Combining these two steps proves the lemma.With the above results in place, we can prove Theorem 4. We will apply the triangle inequality to the telescoping sum for err 𝑘 (𝑟) (Lemma 10) and bound each term by the error of the optimal approximation to 𝑟 (A)b (Lemma 11).Proof of Theorem 4. Focus on a single term in the sum in Lemma 10. First we will get rid of Q and Q T . For 1 ≤ 𝑗 < 𝑞, using that Q T Q = I we have thatEQUATION)Also note that by the convention adopted in Lemma 10, forEQUATION)To see why this is the case, note that because T = Q T AQ, the eigenvalues of T are contained inI = [𝜆 min (A), 𝜆 max (A)].By assumption, the roots of 𝑚 𝑗+1,𝑞 (𝑥) are all real and lie outside of I.Since there is at most one critical point between distinct roots, there can only be one critical point of 𝑚 𝑗+1,𝑞 (𝑥) in I. Thus, there can be no local minima of |𝑚 𝑗+1,𝑞 (𝑥)| in the interior of I. Rather, the minimum of |𝑚 𝑗+1,𝑞 (𝑥)| over I must be attained at the boundary; i.e. at 𝑥 = 𝜆 min or 𝑥 = 𝜆 max .We now apply the triangle inequality to the telescoping sum of Lemma 10:∥err 𝑘 (𝑟) ∥ 2 ≤ 𝑞 ∑︁ 𝑗=1 𝑞 𝑖= 𝑗+1 Q(T -𝑧 𝑖 I) -1 Q T 2 • 𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) 2 .Applying ( 12) and ( 13) we then have∥err 𝑘 (𝑟) ∥ 2 ≤ 𝑞 ∑︁ 𝑗=1 ∥𝑚 𝑗+1,𝑞 (A) -1 ∥ 2 • 𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) 2 .Finally, using Lemma 11 we findEQUATION)We can simplify by noting thatmin deg( 𝑝) <𝑘-(𝑞-𝑗 ) ∥ 𝑝(A)b -𝑟 (A)b∥ 2 ≤ min deg( 𝑝) <𝑘-(𝑞-1) ∥ 𝑝(A)b -𝑟 (A)b∥ 2 ,and we can combine all the condition number factors using𝑞 ∑︁ 𝑗=1 𝜅(A 𝑗 ) 1/2 • 𝜅(𝑚 𝑗+1,𝑞 (A)) ≤ 𝑞 ∑︁ 𝑗=1 𝜅(A 𝑗 ) 𝑞 𝑖= 𝑗+1 𝜅(A 𝑖 ) ≤ 𝑞 𝑞 𝑖=1 𝜅(A 𝑖 ).The result follows by plugging into (14) . □We can bound the error of Lanczos-FA on 𝑓 (𝑥) using triangle inequality as follows:EQUATION)The first and third terms of ( 15) are controlled by the maximum error of approximating 𝑓 (𝑥) with 𝑟 (𝑥) over I. Specifically, if we let ∥𝑟 -𝑓 ∥ I := max 𝑥 ∈ I |𝑟 (𝑥) -𝑓 (𝑥)|, ∥ 𝑓 (A)b -𝑟 (A)b∥ 2 ≤ ∥b∥ 2 • ∥ 𝑓 (A) -𝑟 (A) ∥ 2 ≤ ∥b∥ 2 • ∥𝑟 -𝑓 ∥ Iand similarly, using that Λ(T) ⊂ I,∥lan 𝑘 (𝑟; A, b) -lan 𝑘 ( 𝑓 ; A, b) ∥ 2 = ∥Q𝑟 (T)Q T b -Q 𝑓 (T)Q T b∥ 2 ≤ ∥b∥ 2 • ∥𝑟 -𝑓 ∥ I .The second term of (15) can controlled using (7) This immediately yields near instance optimality in the Euclidean norm:EQUATIONwhere 𝜅(A) is the condition number 𝜆 max /𝜆 min of A. That is, Definition 2 is satisfied with 𝐶 = √︁ 𝜅(A) and 𝑐 = 1. Note that the best polynomial approximation to 1/𝑥 on I = [𝜆 min , 𝜆 max ] already converges at a geometric rate [45] :min deg( 𝑝) <𝑘 max 𝑥 ∈ I |1/𝑥 -𝑝(𝑥)| = 8𝑡 𝑘+1 (𝑡 2 -1) 2 (𝜆 max -𝜆 min ) , 𝑡 := 1 - 2 1 + √︁ 𝜅(A).That is, Fact 3 suffices to prove the exponential convergence of the conjugate gradient method. However, conjugate gradient (and equivalently Lanczos-FA) often converges even faster, which is explained theoretically by the stronger instance-and spectrum-optimality guarantees that the method satisfies [6, 47, 8] .If A is not positive definite, T may have an eigenvalue at or near to zero and the error of the Lanczos-FA approximation to A -1 b can be arbitrarily large. In fact, the same is true for any function 𝑓 (𝑥) which is much larger on I = [𝜆 min , 𝜆 max ] than on Λ, the set of eigenvalues of A. However, while the Lanczos-FA iterates may be bad at some iterations, the overall convergence of Lanczos-FA with 𝑓 (𝑥) = 1/𝑥 is actually good [12] . In particular, the convergence of Lanczos-FA can be related to the MINRES algorithm [15, 49] , which produces an optimal approximation to A -1 b with respect to the A 2 -norm. This allows certain optimality guarantees for MINRES to be transferred to Lanczos-FA, even on indefinite systems. In particular, [12] asserts that for every 𝑘, there exists 𝑘 * ≤ 𝑘 such that7 EQUATION)While (18) does not quite fit the form of Definition 2 because of the 𝑘 * on the left side, it is similar in spirit. Also note that the dependence on 𝑘 in the prefactor √ 𝑘 + 1 is not of great significance. Indeed, the convergence of the optimal polynomial approximation to 1/𝑥 on two intervals bounded away from zero is geometric.Finally, a guarantee for the matrix exponential is proved in [20, (45) ]. They show that the Lanczos-FA iterate satisfies the guarantee∥ exp(-𝑡A)b -lan 𝑘 (exp(-𝑡𝑥); A, b) ∥ 2 ≤ 3∥A∥ 2 2 𝑡 2 max 0≤𝑠≤𝑡 min deg( 𝑝) <𝑘-2 ∥ exp(-𝑠A)b -𝑝(A)b∥ 2 .Again, this bound does not quite fit Definition 2 due to the maximization over 𝑠. The authors of [20] state, "It is not known whether the maximum over 𝑠 ∈ [0, 𝑡] in ( 45) can be omitted and 𝑠 set equal to 𝑡 in the right-hand side."In [11] an algorithm called the Lanczos method for optimal rational function approximation (Lanczos-OR) was developed. For rational functions of the form (4), when run for 𝑘 > deg(𝑛) iterations, Lanczos-OR produces iterateslanOR 𝑘 (𝑟; A, b) := argmin x∈ K 𝑘-⌊𝑞/2⌋ ∥𝑟 (A)b -x∥ |𝑟 (A) | .This implies a 2-norm instance-optimality guarantee (Definition 2):EQUATION)This guarantee is similar to and often somewhat better than Theorem 4. For example, when𝑟 (𝑥) = 1/𝑚(𝑥), √︁ 𝜅(𝑟 (A)) = √︁ 𝜅(A 1 ) • 𝜅(A 2 ) • • • 𝜅(A 𝑞 ).In this case (19) improves on Theorem 4 by a 𝑞 factor and a square root. However, the bound is for a different algorithm; it does not extend to the ubiquitous Lanczos-FA method.Moreover, despite this bound, Lanczos-OR usually performs worse than Lanczos-FA in practice if error is measured in the 2-norm. It is not hard to find examples where (19) is essentially sharp; see for instance Figure 8 . On the other hand, we have been unable to find any numerical examples where Theorem 4 is sharp, suggesting that it may be possible to prove a tighter bound for Lanczos-FA.The convergence of Lanczos-FA is entirely determined by spectral properties of A. Therefore, following the classical analysis of 𝑓 (𝑥) = 1/𝑥, we can relax the notion of instance optimality (Definition 2) by removing its dependence on b: Definition 12 (Near Spectrum Optimality). For an input instance ( 𝑓 , A, b, 𝑘), we say that a Krylov method is nearly spectrum optimal with parameters 𝐶, 𝑐 if∥ 𝑓 (A)b -alg 𝑘 ( 𝑓 ; A, b) ∥ 2 ≤ 𝐶 ∥b∥ 2 min deg( 𝑝) <𝑐𝑘 ∥ 𝑓 (A) -𝑝(A) ∥ 2 .Note that Definition 12 depends only on the spectrum of A, and not on the interaction of the eigenvectors of A with the starting vector b. Hence, we call it "spectrum optimality". Note also that the guarantee of Theorem 6 fits this form. We can further relax this notion of optimality by weakening its dependence on A: Definition 13 (Near FOV Optimality). For an input instance ( 𝑓 , A, b, 𝑘), we say that a Krylov method is nearly FOV optimal with parameters 𝐶, 𝑐 if∥ 𝑓 (A)b -alg 𝑘 ( 𝑓 ; A, b) ∥ 2 ≤ 𝐶 ∥b∥ 2 min deg( 𝑝) <𝑐𝑘 max 𝑥 ∈ [𝜆 min ,𝜆 max ] | 𝑓 (𝑥) -𝑝(𝑥)| .Note that Fact 3 fits this form. Each type of optimality tightly relaxes the previous one. Definition 2 implies Definition 12 and, as we show in Theorem 14, for any 𝑓 , 𝑘 and A, there exists a "worst-case" choice of b for which their bounds coincide; likewise, Definition 12 implies Definition 13, and for any 𝑓 (𝑥) and 𝑘 there exists a "worst-case" choice of A and b for which their bounds coincide. Theorem 14.1. Given any 𝑑, discrete set Λ of at most 𝑑 real points, 𝑓 (𝑥), and 𝑘 < 𝑑, there exists a symmetric matrix A ∈ R 𝑑×𝑑 and vector b ∈ R 𝑑 such that the spectrum of A is Λ and min We would like to find b so that 𝑓 (𝜆 𝑖 ) -𝑝(𝜆 𝑖 ) = (-1) 𝑖-1 𝜖; i.e. so that 𝑝 = 𝑝 * . When b is fixed, for each 𝑗 = 0, 1, . . . , 𝑘 -1 the solution to this least squares problem must satisfyEQUATIONEQUATIONWhen 𝑝 = 𝑝 * , this gives the conditions0 = -2 𝑘+1 ∑︁ 𝑖=1 𝑏 2 𝑖 (-1) 𝑖-1 𝜖𝜆 𝑗 𝑖 , 𝑗 = 0, 1, . . . , 𝑘 -1.Without loss of generality, we can assume ∥b∥ 2 = 1 so that 𝑏 2 1 + • • • + 𝑏 2 𝑘+1 = 1. Thus, we obtain a linear system         1 1 • • • 1 -2𝜖𝜆 0 1 2𝜖𝜆 0 2 • • • 2(-1) 𝑘+1 𝜆 0 𝑘+1 𝜖 . . . . . . . . . -2𝜖𝜆 𝑘-1 1 2𝜖𝜆 𝑘-1 2 • • • 2(-1) 𝑘+1 𝜖𝜆 𝑘-1 𝑘+1                   𝑏 2 1 𝑏 2 2 . . . 𝑏 2 𝑘+1          =         1 0 . . . 0         .We can rewrite this system as         1 -1 • • • (-1) 𝑘 𝜆 0 1 𝜆 0 2 • • • 𝜆 0 𝑘+1 . . . . . . . . . 𝜆 𝑘-1 1 𝜆 𝑘-1 2 • • • 𝜆 𝑘-1 𝑘+1                   𝑏 2 1 -𝑏 2 2 . . . (-1) 𝑘 𝑏 2 𝑘+1          =         1 0 . . . 0         .This system can be solved analytically via Cramer's rule and has solution𝑏 2 ℓ = 𝑘+1 𝑖=1 𝑖≠ℓ 𝑘+1 𝑗=𝑖+1 𝑗≠ℓ (𝜆 𝑗 -𝜆 𝑖 ) 𝑘+1 ∑︁ 𝑚=1 𝑘+1 𝑖=1 𝑖≠𝑚 𝑘+1 𝑗=𝑖+1 𝑗≠𝑚 (𝜆 𝑗 -𝜆 𝑖 ) .Clearly (𝜆 𝑗 -𝜆 𝑖 ) is positive for 𝑗 ∈ {𝑖 + 1, . . . 𝑘 + 1}. Thus the numerator and denominator above are positive, so the entries of b are well-defined and real. This implies that, for these choices of A and b,min deg( 𝑝) <𝑘 ∥ 𝑓 (A)b -𝑝(A)b∥ 2 2 = min 𝛼 0 ,..., 𝛼 𝑘-1 𝑘+1 ∑︁ 𝑖=1 𝑏 2 𝑖 𝑓 (𝜆 𝑖 ) -𝑝(𝜆 𝑖 ) 2 = 𝑘+1 ∑︁ 𝑖=1 𝑏 2 𝑖 𝜖 2 = 𝜖 2 .Taking the square root of both sides gives the result. □We also note that, with some additional assumptions on b, spectrum optimality implies instance optimality:Lemma 15. Let {u 1 , . . . , u 𝑑 } be the eigenvectors of A. Given a problem instance ( 𝑓 , A, b, 𝑘), if an algorithm is nearly spectrum optimal with parameters 𝐶 and 𝑐, then it is nearly instance optimal with parameters 𝐶 • ∥b∥ 2 min 𝑗 |u T 𝑗 b| and 𝑐.The bound is useful e.g., when b is a random vector. For example, when b has independent and identically distributed Gaussian entries, ∥b∥ 2 min 𝑗 |u T 𝑗 b| = 𝑂 (𝑑 3/2 ) with high probability. Such random vectors occur when sampling Gaussians [59] and are extremely common in machine learning applications related to trace and spectrum approximation [58, 32, 69, 7, 13, 14] .Let V be the matrix whose 𝑖th column is v 𝑖 . Let 𝑤 𝑖 = v T 𝑖 b and w = V T b be the vector whose 𝑖th entry is 𝑤 𝑖 . Then,∥ 𝑓 (A)b -𝑝(A)b∥ 2 2 = 𝑑 ∑︁ 𝑖=1 ( 𝑓 (𝜆 𝑖 ) -𝑝(𝜆 𝑖 )) 2 𝑤 2 𝑖 ≥ min 𝑗 𝑤 2 𝑗 𝑑 ∑︁ 𝑖=1 ( 𝑓 (𝜆 𝑖 ) -𝑝(𝜆 𝑖 )) 2 . Clearly 𝑑 𝑖=1 ( 𝑓 (𝜆 𝑖 ) -𝑝(𝜆 𝑖 )) 2 ≥ max 𝑥 ∈Λ | 𝑓 (𝑥) -𝑝(𝑥)| 2 .Taking the square root of both sides and substituting into Definition 12 proves the result.For completeness, we now show that if b ∼ N (0, I 𝑑 ), then with high probability,∥b∥ 2 min 𝑗 |v T 𝑗 b| = 𝑂 (𝑑 3/2 ).First, with high probability, ∥b∥ 2 = Θ( √ 𝑑); see, for example, [66, p. 3.1.2] . Second, we show that with high probability |v T 𝑗 b| = Ω(1/𝑑) for all 𝑗. Since V is orthonormal, w := V T b ∼ N (0, I 𝑑 ). By anti-concentration of the normal distribution, the probability that |𝑤 𝑗 | > 𝜖 is at least 1 -0.4𝜖 for any 𝜖. By a union bound, this holds simultaneously for all 𝑗 with probability at least 1 -0.4𝜖 𝑑. Setting 𝜖 = Θ(1/𝑑) finishes the argument. Finally, by another union bound, our bounds on the numerator and on the denominator hold simultaneously with high probability.We begin by quoting bounds from [10] : Lemma 16. For all 𝑘 ≥ 1, the Lanczos-FA iterate satisfies the bounds1. ∥A 1/2 b -lan 𝑘 (𝑥 1/2 ; A, b) ∥ 2 ≤ 𝜆 3/2 max 2𝑘 3/2 • ∥A -1 b -lan 𝑘 (1/𝑥; A, b) ∥ 2 . 2. ∥A -1/2 b -lan 𝑘 (𝑥 -1/2 ; A, b) ∥ 2 ≤ √︂ 𝜆 max 𝜋𝑘 • ∥A -1 b -lan 𝑘 (1/𝑥; A, b) ∥ 2 .Proof. For Part 1, see Example 4.1 in [10] . For part Part 2, we use the same proof again but substituting the inverse square root for the square root. For both parts, we have simplified the resulting bounds using the fact that for 𝑘 ≥ 1,Γ(𝑘 -1/2) Γ(𝑘 + 1) ≤ √ 𝜋 𝑘 3/2 Γ(𝑘 + 1/2) Γ(𝑘 + 1) ≤ 1 √ 𝑘 . □Next, we bound the error of Lanczos-FA on linear systems by the error of the optimal polynomial approximation to 𝑥 -1/2 : Lemma 17. For all 𝑘 ≥ 1, the Lanczos-FA iterate satisfies the bounds∥A -1 b -lan 𝑘 (1/𝑥; A, b) ∥ 2 ≤ 3 √ 𝜆 min √︁ 𝜅(A) ∥b∥ 2 min deg( 𝑝) <𝑘/2 max 𝑥 ∈Λ 1 √ 𝑥 -𝑝(𝑥) . Proof. Let 𝑝 * (𝑥) = argmin deg( 𝑝) <𝑘/2 max 𝑥 ∈Λ 1 √ 𝑥 -𝑝(𝑥)and note that 𝑝(𝑥) 2 is a polynomial of degree less than 𝑘. Therefore,min deg( 𝑝) <𝑘 ∥A -1 b -𝑝(A)b∥ 2 ≤ ∥b∥ 2 min deg 𝑝<𝑘 max 𝑥 ∈Λ 1 𝑥 -𝑝(𝑥) ≤ ∥b∥ 2 max 𝑥 ∈Λ 1 𝑥 -𝑝 * (𝑥) 2 . Thus, since |1/𝑥 -𝑝 * (𝑥) 2 | = |1/ √ 𝑥 + 𝑝 * (𝑥)| • |1/ √ 𝑥 -𝑝 * (𝑥)|,we can plug the above into (17) to obtain a bound∥A -1 b-lan 𝑘 (1/𝑥) ∥ 2 ≤ √︁ 𝜅(A) ∥b∥ 2 max 𝑥 ∈Λ 1 √ 𝑥 + 𝑝 * (𝑥) max 𝑥 ∈Λ 1 √ 𝑥 -𝑝 * (𝑥) .Now use can use the optimality of 𝑝 * (𝑥)in approximating 1/ √ 𝑥 on Λ to bound:max 𝑥 ∈Λ 1 √ 𝑥 + 𝑝 * (𝑥) = max 𝑥 ∈Λ 2 √ 𝑥 + 𝑝 * (𝑥) - 1 √ 𝑥 ≤ max 𝑥 ∈Λ 2 √ 𝑥 + max 𝑥 ∈Λ 𝑝 * (𝑥) - 1 √ 𝑥 ≤ 2 √ 𝜆 min + max 𝑥 ∈Λ 0(𝑥) - 1 √ 𝑥 ≤ 3 √ 𝜆 min .Substituting this inequality above proves the lemma. □The main proofs now follow directly.Proof of Theorem 6. Substitute Lemma 17 into Lemma 16, part (b) . □ To understand Theorems 6 and 7, we repeat the experiment using the inverse square root and square root functions. We reuse the second and third A matrix and b vectors from the previous experiment. As Figure 7 shows, our bounds are tighter than Fact 3. They closely resemble the true convergence of Lanczos-FA, but stretched horizontally by a factor of 2. This is because the degree of the polynomial minimization in both bounds is 𝑘/2, while in these examples Lanczos-FA performs nearly instance optimally (that is, as well as the best degree 𝑘 polynomial). Still, our bounds capture the correct qualitative behavior of the algorithm.In Theorem 4, we assume that the poles of the rational function 𝑟 (𝑥) lie outside the interval I = [𝜆 min , 𝜆 max ] containing A's eigenvalues. If the poles of 𝑟 (𝑥) live in I, then the Lanczos-FA iterate The maximum observed ratio between the error of Lanczos-OR and the optimal error over choice of right hand side b when approximating A -𝑞 for matrices with varying condition number 𝜅. Each point shows the optimality ratio for a different pair of 𝜅 and 𝑞. Points with the same color correspond to the same value of 𝜅. On the left, the dotted line plots 𝑔(𝑞) = 𝜅 𝑞/2 for the maximum 𝜅 considered (10 6 ). On the right, the dotted line plots 𝑔(𝜅) = 𝜅 𝑞/2 for the maximum 𝑞 considered (2 6 = 64). Overall, the optimality ratio appears to grow as Ω(𝜅 𝑞/2 ). Contrast with Figure 3 .can be arbitrarily far from the optimal iterate. Indeed, an eigenvalue of T might be very close to a pole, causing 𝑓 (T) to be poorly behaved. This behavior is easily observed e.g. for 𝑓 (A) = A -1 and rules out a direct analog of Theorem 4 when 𝑟 (𝑥) has poles in I. However, as noted in (18) , for 1/𝑥 there exists bounds for Lanczos-FA in terms of the best possible KSM [12] .However, as discussed in Appendix B.1, the "overall" convergence of Lanczos-FA still seems to closely follow the optimal approximation for many matrix functions. Specifically, even if the Lanczos-FA iterate deviates significantly from optimal on some iterations, there are other iterations where it is very close to optimal. We illustrate this phenomena in Figure 6 for two rational functions with poles in I = [𝜆 min , 𝜆 max ], as well as the function sign(𝑥), which has a discontinuity in I and would typically be approximated by a rational function with conjugate pairs of imaginary poles on the imaginary axis which become increasingly close to the the interval as the rational function degree increases.8 As discussed in Appendix B.2, the Lanczos-OR method is an alternative method for rational matrix function approximation for which a tighter guarantee than Theorem 4 is currently known (the iterates are optimal in a certain norm). However, Lanczos-FA usually outperforms Lanczos-OR when measured in the 2-norm. For example, as discussed in Section 4.1, when approximating A -𝑞 b, the worst optimality ratio of Lanczos-FA that we were able to observe was 𝑂 ( √︁ 𝑞 • 𝜅(A)), much lower than Theorem 4 would suggest). Repeating the same experiment with Lanczos-OR shows that the method's optimality ratio appears to grow as Ω(𝜅(A) 𝑞/2 ) (see Figure 8 ).Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We release our code in the supplementary material and on GitHub. In addition, details of the experiments are provided in the text.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
outlook: 
 This paper provides instance-optimality guarantees for Lanczos-FA applied to a range of rational functions. We conclude with open questions that we believe are worthy of further study.Extension to other function classes. Empirically, Lanczos-FA seems to be nearly instance optimal for a wide variety of functions beyond those considered in this paper, such as rational functions with conjugate pairs of complex poles whose real parts lie outside [𝜆 min , 𝜆 max ]. As seen in Figure 6 , the error of Lanczos-FA on functions with real poles in [𝜆 min , 𝜆 max ] is intriguing, oscillating between being very large and nearly optimal. We discuss this more in Appendix E.2. It would be valuable to provide bounds explaining these behaviors.It would be also natural to try to extend our bounds to Stieltjes/Markov functions, which can be viewed as a certain type of infinite degree rational function approximations with poles in (-∞, 0], and includes important functions like the inverse square root and a shifted logartihm. Our bound Theorem 4 cannot be directly applied to this class due to the dependence on the rational function denominator degree 𝑞.Construction of hard instances / refined upper bounds. Theorem 4 has an exponential dependence on the degree of the rational function's denominator 𝑞, which limits the practicality of our bounds. It is unclear if and when this dependence can be improved. The experiment in Section 4.1 provides strong evidence that some dependence on 𝑞 is necessary, but the hardest examples we have depend on √ 𝑞, instead of the current bound of 𝜅(A) 𝑞 guaranteed by Theorem 4.It is an open question whether Theorem 4 can be tightened, or whether matching hard instances exist.Finite precision arithmetic. Our analysis concerns the behavior of the Lanczos algorithm when run in exact arithmetic. In practice, the implementation of the Lanczos algorithm is very important; for instance, practical implementations often output a Q which is far from orthogonal [50, 8] . While this instability can be mitigated with more expensive implementations, theoretical work shows that, surprisingly, Lanczos and Lanczos-FA can work well despite it [57, 56, 55, 33, 21, 20] . For example, [21, 52, 9] show that Fact 3 still holds up to a close approximation in finite precision arithmetic for any bounded matrix function. It would be valuable to study whether stronger near-optimality guarantees like those proven in Theorem 4 are also robust to finite precision. For 𝑓 (𝑥) = 1/𝑥, this problem has been studied in [33] .We first introduce notation used throughout. Given a rational function 𝑟 (𝑥) = 𝑛(𝑥)/𝑚(𝑥) with numerator degree 𝑝 denominator degree 𝑞, for 1 ≤ 𝑖 ≤ 𝑗 ≤ 𝑞, we define:𝑚 𝑖, 𝑗 (𝑥) := 𝑗 𝑘=𝑖 (𝑥 -𝑧 𝑘 ).We adopt the convention that 𝑚 𝑗+1, 𝑗 (𝑥) := 1. Note that 𝑚 𝑖, 𝑗 is a ( 𝑗 -𝑖 + 1)-degree polynomial. We begin with a few standard results that will be useful for the proof of Theorem 4. Lemma 8 ( [22, 61] ). A 𝑗 b = QQ T A 𝑗 b = QQ T AA 𝑗 -1 b = QQ T AQQ T A 𝑗 -1 b = QQ T AQ • • • Q T AQQ T b.Using that Q T AQ = T, we find that A 𝑗 b = QT 𝑗 Q T b, and thus, by linearity, 𝑛(A)b = Q𝑛(T)Q T b = lan 𝑘 (𝑛). □ Lemma 9. Let A 𝑗 be as in (5) . Then, for any 𝑘 ≥ 0, opt 𝑘 (𝑟 𝑗 ,EQUATIONRecall thatA 𝑗 = ±(A-𝑧 𝑗 I). Since Q T AQ = T and Q T Q = I, we have Q T A 𝑗 Q = ±(Q T (A-𝑧 𝑗 I)Q) = ±(T -𝑧 𝑗 I).Noting also that A 𝑗 𝑟 𝑗 (A) = ±𝑟 𝑗 -1 (A) and plugging into (9) gives the result. □ A.3 A telescoping sum for the error in terms of opt 𝑘 (𝑟 𝑗 , A 𝑗 )Our first main result is a decomposition for the Lanczos-FA error. Lemma 10. Suppose 𝑘 > deg(𝑛). Then,𝑟 (A)b -lan 𝑘 (𝑟) = 𝑞 ∑︁ 𝑗=1 𝑞 𝑖= 𝑗+1 Q(T -𝑧 𝑖 I) -1 Q T 𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) .where we adopt the convention that 𝑞 𝑖=𝑞+1 B 𝑖 = I for any set of matrices {B 𝑖 }.Proof. We can decompose err 𝑘 (𝑟 𝑗 ) asEQUATIONFocusing on the second term and using Lemma 9,opt 𝑘 (𝑟 𝑗 , A 𝑗 ) -Q𝑟 𝑗 (T)Q T b = Q(T -𝑧 𝑗 I) -1 Q T 𝑟 𝑗 -1 (A)b -Q(T -𝑧 𝑗 I) -1 𝑟 𝑗 -1 (T)Q T b = Q(T -𝑧 𝑗 I) -1 Q T 𝑟 𝑗 -1 (A)b -Q𝑟 𝑗 -1 (T)Q T b = Q(T -𝑧 𝑗 I) -1 Q T err 𝑘 (𝑟 𝑗 -1 ). Substituting this into (10), we haveEQUATIONNext, notice that opt 𝑘 (𝑟 1 , A 1 ) is exactly the Lanczos approximation to 𝑟 1 (A)b. Indeed, since Q T Q = I, Lemmas 8 and 9 implylan 𝑘 (𝑟 1 ) = Q(T -𝑧 𝑖 I) -1 𝑛(T)Q T b = Q(T -𝑧 𝑖 I) -1 Q T Q𝑛(T)Q T b = Q(T -𝑧 1 I) -1 Q T 𝑛(A)b = opt 𝑘 (𝑟 1 , A 1 ). Using this as a base case, we can repeatedly apply our decomposition of err 𝑘 (𝑟 𝑗 ) in ( 11) to obtainerr 𝑘 (𝑟) = err 𝑘 (𝑟 𝑞 ) = 𝑞 ∑︁ 𝑗=1       𝑞 𝑖= 𝑗+1 Q(T -𝑧 𝑖 I) -1 Q T       𝑟 𝑗 (A)b -opt 𝑘 (𝑟 𝑗 , A 𝑗 ) . □ A.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We provide our code in the supplementary material and on GitHub. The code to produce Figure 5 is not released, as it was shared with us privately by the authors of the paper in which it first appeared [44] . • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: These are described in the text and the code is included in the supplementary materials.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [No] Justification: The algorithms we test are not random and no sampling is performed. Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Justification: This paper provides new theoretical analysis of an old and widely used algorithm, the Lanczos method. The goal is to achieve a better scientific understanding of the method. The Lanczos method has been used in a huge variety of applications across machine learning and scientific computing, and thus has societal impact, but the results and focus of this paper do not directly relate to this impact.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.We choose to measure error in the Euclidean norm, and thus define optimality with respect to this norm. While other norms have been considered in prior work on matrix-function approximation[11], the Euclidean norm a simple starting point.The A-norm is defined for positive definite A by ∥x∥ A = ∥A 1/2 x∥ 2 .Code for our experiments is available at https://github.com/NoahAmsel/lanczos-optimality/ tree/neurips2024_near_optimality..For indefinite matrices, 𝜅(A) denotes the ratio of the largest eigenvalue magnitude to the smallest eigenvalue magnitude.We remark that[11] shows that applying their Lanczos-OR method to each term in the partial fraction decomposition of the approximating rational function yields an approximation to the sign function that seems to avoid the oscillations of Lanczos-FA. 
 
 Appendix:  


Decision: The presented paper studies the approximation of the matrix function using a Lanczos-based method. It shows that, for a natural class of rational functions, Lanczos matches the error of the best possible Krylov subspace method, up to a multiplicative approximation factor.

Five reviewers evaluated the paper, and their overall assessment is positive. I agree with their evaluation and believe the paper makes a significant contribution with compelling results. In particular, I think the presentation of the paper is truly exceptional. Some reviewers raised concerns about the applicability of the proposed bounds in finite precision arithmetic, which the authors addressed satisfactorily.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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?
limitations: limitations: Nothing to add.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: Congratulations on this paper.
limitations: 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.
paper_summary: 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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Limitations are acknowledged. (I discuss this under "Weaknesses" above.)
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: The authors discuss limitations in Section 4.

Comments: comment: Thank you for the answers. I think some form of them should be included in the revised manuscript.

My score was already positive before (7 - accept), and stays the same after reading the rebuttal.
Thank you for the rebuttal. After reading the rebuttal and reviews from other reviewers, I decided to raise my score.
Thank you for answering my questions. I like your paper. To make a clear statement, I will increase my score to accept.
Thank you for iterating!

I agree with your perspective on exact versus finite-precision arithmetic. Nonetheless, assuming exact arithmetic remains a weakness of the analysis (though typical for this type of work).
I also agree with the rebuttal's discussion on the constant in Theorem 1. However, this constant also remains a weakness of the theory, even though there is hope that the bound can be tightened.

Finally, about the matrix function experiments: my review might have been poorly phrased; apologies for that. What it referred to was not that the matrix function was missing but its application. For example, the current experiments include log-determinant estimation in Figure 1, but only on a toy matrix, whereas a case study in Gaussian process regression would strengthen the paper's connection to the ML literature. (Same for the matrix sign or  matrix exponential, for example.)

Altogether, I continue to recommend accepting the submission. Thank you again for the reply.