Computing Higher Order Derivatives of Matrix and Tensor Expressions
Optimization is an integral part of most machine learning systems and most numerical optimization schemes rely on the computation of derivatives. Therefore, frameworks for computing derivatives are an active area of machine learning research. Surprisingly, as of yet, no existing framework is capable of computing higher order matrix and tensor derivatives directly. Here, we close this fundamental gap and present an algorithmic framework for computing matrix and tensor derivatives that extends seamlessly to higher order derivatives. The framework can be used for symbolic as well as for forward and reverse mode automatic differentiation. Experiments show a speedup of up to two orders of magnitude over state-of-the-art frameworks when evaluating higher order derivatives on CPUs and a speedup of about three orders of magnitude on GPUs.
The paper presents an algorithm for computing higher order derivatives of multiple outputs, by translating matrix expressions into Ricci calculus, to generalize modern frameworks for automatic differentiation from first order derivatives of scalar outputs to higher order derivatives of multiple outputs.   Overall comments ---------------- I really enjoyed the core idea of this paper; a generalized form of autograd has immense potential to increase accessibility to many higher order optimization methods by removing the implementation barrier, a benefit that many gradient-based optimization procedures enjoy today. The introduction to Ricci calculus was also easy to read, and the tensor calculus algorithm is easy to understand.   However, I have a number of concerns on the submitted paper, largely regarding the experiments presented in the paper.   1) The paper describes a forward mode, but does not present any sort of evaluation thereof. Jacobians and higher order derivatives are mentioned in the introduction but the experiments focus solely on Hessian computation. The proposed method claims to be able compute derivatives of non-scalar valued functions, but the experiments only demonstrate the approach on scalar-valued functions. The paper would be much stronger if the empirical results matched the described abilities.   2) The main paper claims even better speed up on the GPU. Why do the authors instead present the supposedly worse CPU results up front?  3) I could not find many details regarding the experimental setup, e.g. where the data for the problem came from, whether they are real or synthetic, how the problems are generated if synthetic, etc.  4) There is some strange behavior in Figure 2 of the supplemental material. The authors write that the worse performance of Tensorflow and PyTorch is due to unavoidable data transfer from the main memory and the GPU. However, for some reason PyTorch doesn't suffer from this (but tensorflow does) in only the left-most plot. Why is this the case? Also, within these two frameworks, it should be possible to transfer all data to the GPU before timing the functions, and it is definitely possible to directly allocating all future tensors on the GPU, without needing intermediate data transfers. If the authors believe this is not possible, please elaborate why.   5) The authors point out that one of the drawbacks of existing tools is the creation of enormous computational graphs when computing Hessians. However, the authors explicitly do not report the time for constructing the expression graphs on line 287. For better empirical motivation, the paper should presents timing results that quantify and back up this statement. The results should also compare to the baseline approach of computing the terms based on a formula derived by hand to demonstrate how much (or little) overhead the proposed algorithm has.   Overall, while I enjoyed the exposition on Ricci calculus and automatic differentiation, it is perhaps too verbose, since the paper leaves very little room for experimental justification. This results in a paper that, while well motivated, is experimentally weak. While the few experiments presented do show promise, I cannot recommend acceptance solely based on this, as a much more compelling case can likely be given. Hopefully the authors can shed some light in the rebuttal, as the work here seems to be an important next step in autodifferentiation tools for the machine learning community.   Minor comments -------------- a) Can you elaborate more on the translation to and from Ricci calculus? To actually compute the terms, are expressions translated back into matrix algebra before being evaluated, or are you evaluating the Ricci calculus expressions directly? When you evaluate the Ricci expressions, how do you decide an order of evaluation? For tensor expressions, such choices can greatly effect the actual computational cost of evaluating the expression.   b) Consider include benchmarking results on computing Hessian-vector products, which is also a common use-case when the explicit Hessian cannot be formed or directly decomposed (e.g. due to memory or computational constraints).   c) In the web demo, it would be nice to include more objectives of the mentioned 'classical' machine learning problems (listed in lines 276-277) as examples, as well as examples which compute Hessians as opposed to gradients, and examples which compute non-scalar outputs. It also appears that there is no max operator.   Quality ------- Overall the experiments section is much poorer in quality, as described in this review.   Clarity ------- I found the majority of the main paper to be clear and well-written, with one major exception: the experiments section. Specifically, the `Results' paragraph is extremely poorly written, with most of the sentences not being well-formed.   One other major point of clarity is that there is a mismatch between the statements in the conclusion and the experiments. The conclusion claims that the approach achieves state of the art performance for first order derivatives, while the experiments merely claim that 'basically, all frameworks are equally fast'. The plots in the Appendix do not back up the conclusion.   minor suggestions for main paper:  -On line 115, it may not be clear to readers what it means to 'transform contravariantly' or 'transform covariantly' -The last sentence in line 273-274 does not make sense.  -While 'probably' and 'basically' are not necessarily bad to use in general, their usage in the experimental section is not great  -Figure 3 needs to say how large n is, which I could only found in the Appendix.  -The sentence ending on line 232 is missing a period.  -On line 322, 'in case of' should be 'in the case of'  minor suggestions for appendix:  -Section 4 of the experiments refer to 'badges' of experiments, this should probably be 'batches' -There is a space missing in the description of the second set of experiments -Tables 5,6, the meaning of, e.g., 'k in 1000', is not clear.  -In Figure 1, for logistic regression, it is very difficult to see the line for theano.   Originality ----------- The the originality of the work is to show that a combination of two well-known ideas, Ricci calculus and automatic differentiation, can result in faster, smaller computational graphs that can compute higher order derivatives.   Significance ------------ The core idea here has much potential for the machine learning community at large, but the experiments seem more like preliminary results and could be much stronger.   Post-rebuttal update =============================== While the rebuttal does clear up certain questions, the paper still needs work on its empirical motivation. Though I believe this work has great potential, my assessment of the paper remains the same for the following primary reason:  Any notion of including additional experiments (which is also brought up by another reviewer) to better motivate the work is completely absent in the rebuttal. While the authors argue that their synthetic experiments on three toy problems are enough, they are quite far removed from realistic problems where autodifferentiation with higher order methods would actually be useful. If the authors are going to evaluate on problems that are trivial to solve with typical second order approaches, they need to compare with the typical baseline approach and not just an auto-diff strawman that most people wouldn't use to solve the problem.   In further revisions, I would suggest that the authors seriously consider the following:   1) Formally present the cost of creating the computational graph. While it may seem insignificant to you, the reality is that many second order methods are derived and implemented directly, and not with auto-diff, and so this is the overhead that matters to many people.   2) Include the exact experimental setup for generating the benchmarks. Running time *can* in fact depend on whether the data is synethetic or not; oftentimes real data is sparse or structured, which is often exploited when people implement second order methods. The auto-diff runtime may not be so great if it doesn't exploit various cost-saving structural shortcuts that are common to use in practice.   3) Alternatively, instead of comparing to problems which are trivial to solve without auto-diff, evaluate in a setting where people actually use second order auto-differentiation (e.g. double backprop).