Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new gradient-based learning algorithm for recurrent neural networks, making use of the directional derivative along a candidate direction. The directional derivative serves the purpose of improving the usefulness of a given candidate direction for gradient-based parameter updates by computing the projection of the gradient along the given direction. The candidate direction can come from various sources such as randomly sampled directions, truncated backpropagation through time (BPTT), the “Reptile” meta-learning approach by Nichol et al. (2018), or synthetic gradients. The authors call this technique “deep online directional gradient estimate” (DODGE) and demonstrate it in several experiments including a copy task (Graves et al. 2014) and a NeRF task (Mildenhall et al. 2020).
main_review: Strengths:

- The paper is working on a new approach to gradient-based optimization for recurrent architectures and doing this with an approach that is refreshing to see.

- The paper has empirical evidence that the proposed method works across a range of gradient estimators from BPTT, Reptile etc.

Weaknesses:

- One of the main concerns I have with the paper is the assertion that computing the directional derivative has “computational cost the same as the forward computation of the function”, which the authors mention several times in the paper, referring to the cost of computing the directional derivative with forward mode automatic differentiation. I believe this doesn’t cover the full picture and can be misunderstood by the reader. 

I think what the authors mean by this statement is what they describe in section 3.2: that the directional derivative can be computed with cost of O(p) per time step where p is the size of the parameter vector with respect to which the gradient is computed, and this has the same computational complexity with the forward computation of the original function (without the derivative). This might be correct, but it doesn’t mean that the directional derivative can be computed for free with a “computational cost the same as the forward computation of the function” which to me seems to imply that both the function and the directional derivative can be computed without any extra computational cost compared with just the forward computation of the original function (without the derivative). In other words, I believe that when computing the directional derivative and the original function together, as it happens during forward mode automatic differentiation, the cost is indeed more (up to double) compared with the computation of the original function (without the derivative). In any case, it would be good if the authors clarify these points in the paper overall.

- In Section 2, it would really help to have a figure explaining the dependencies between x_t, l_t, etc. in the BPTT and synthetic gradient explanations in equations 1 and 2.

- In Section 2, synthetic gradients, can you give a bit more detail about how the bootstrapped terms explained immediately after equation 2 are used in practice in an implementation?

- In Section 2, real-time recurrent learning, the notation of z = h_T(...(h_1 (y)) … ) is slightly out of place given the use of x, l, w, etc. up to that point. 

summary_of_the_review: I have a positive view of this paper and the line of research the authors are working on. I believe there is a lot of value in revisiting earlier work such as real-time recurrent learning (RTRL) (Williams & Zipser, 1989), which the authors correctly identify as a related work and explain in their manuscript.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes directional gradient descent as a way to approximate 
the gradient in recurrent learning. Directional gradient descent
uses a candidate direction (e.g., a random vector or a biased gradient
estimate) and then "corrects" that estimate by scaling it with the
directional derivative, i.e, the inner product between the candidate 
direction and the true gradient (or an unbiased estimate thereof).
main_review: The idea is simple and intuitive: Any vector $u$ can be turned into a
descent direction by computing
$\langle \nabla L(w), u \rangle u$, where the inner product may be obtained at a lower cost than computing
the gradient $\nabla L(w)$ itself.

This idea has been known in the optimization literature as a "sketch and
project" gradient estimate (see, e.g., [1] and citations therein).
This line of work should be cited and duly acknowledged.
To my knowledge, it hasn't been studied specifically in the context of
recurrent ML architectures, so a paper like the present one could still have its merits.

The computational cost of the proposed approach is not discussed in 
sufficient detail. 
While the memory savings compared to (T)BPTT
are apparent, I don't see a reason why the *computational* complexity would
be any lower. 
We are still relying on a gradient computation of $\frac{dx_t}{dw}$, even if 
we immediately project that partial derivative onto the candidate direction.
Unless I am missing something, this cost is *added* to the cost of computing
the candidate direction.
That means that using directional gradient trick in conjunction with a candidate
direction based on TBPTT/DPG/SYN would (at least) double the computational
cost. Could the authors please clarify this aspect?

The experimental comparison is a bit lacking in my opinion. 
On every problem, only one competing method is compared to. Why not report
the performance of all baseline methods for each test problem?

Except for the lacking discussion of computational cost, the paper is clear and well-written.


[1] https://proceedings.neurips.cc/paper/2018/file/fc2c7c47b918d0c2d792a719dfb602ef-Paper.pdf
summary_of_the_review: Essentially, the paper is applying the known "sketch and project" trick
to recurrent learning, so the novelty is rather limited. The experimental
comparison is a bit lacking in my opinion and there is a big question mark in terms of the added computational cost
(and whether that is worth it in practice). I am recommending rejection
for now, but would encourage the authors to respond to my concerns in the rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to adapt the RTRL technique when training RNNs to make it usable in practice. That is, instead of computing the full gradient of the loss $L$ according to all parameters, the proposed method "DODGE" consists in computing the gradient of $L$ in *one* or a small number of directions in the parameter space. These "directional gradients" of $L$ are much easier to compute than the full gradient when using RTRL. More precisely, the user can choose a subspace $\mathcal{P}'$ (of dim. $p'$) of the space of parameters $\mathcal{P}$ (of dim. $p$), and compute the projection of the true gradient $g^*$ of $L$ on the space $\mathcal{P}'$, *with a computational cost proportional to $p'$*. This is advantageous when $p' \ll p$.

Notably, this method can be used in two ways:
 * estimating the true gradient by computing its projection on a random low-dimensional subspace of the parameters;
 * improve an existing estimation $\hat{g}$ of the true gradient $g^*$ by computing the projection of $g^*$ on $\hat{g}$: this projection has better properties than $\hat{g}$.
main_review: # Preliminary remarks

The proposed method is surprisingly simple. But it seems that, after a quick search, nothing close has been proposed before. I did not find any reference to methods mixing "directional gradient/derivative", "Monte Carlo estimation of the gradient", etc.

So, despite its simplicity, "DODGE" seems to be quite new. However, I might have missed some references.

Reference about "random coordinate descent", close to the main idea of the paper : *Langevin Monte Carlo: random coordinate descent and variance reduction*, Ding 2021.

# Strengths

The simplicity of the method is one of its main strengths. The idea of projecting the true gradient on an estimated gradient is the main practical application of the paper. The author show is one specific case that DODGE + synth. grads is better than synth. grands alone (Fig. 4). 

# Weaknesses

The range of experiments is very narrow. The reader may expect more datasets for the same setup, in order to show that the results are consistent over *several* tasks and datasets (and not only one per setup).

# Clarity

Overall, the paper is easy to follow. However:
 * there are many typos (see below);
 * the "Related work" section may be placed just after the introduction. Since the proposed technique is surprisingly simple, the reader would expect a quick review of related papers very early in the article (and not at the end);
 * I would not recommend the use of a Jax code excerpt on page 4 (the reader is supposed to know how it works). Pseudo-code would be preferable, and this except could be put in the Appendix.

# Typos

* p 3: "for any $u$" => "for any unitary $u$"
* p 4: in the code excerpt: "gradient_estimate" becomes "grad_estimate"
* p 4: "ORACLE": bad alignment
* end of p 5: "<=" => "$\leq$"
* p 6, Sec. 5.2: "RTRL": bad alignment
* p 8: fig. 2: titles: "max_truc_len" => "max_trunc_len"
summary_of_the_review: The idea is new, simple, relatively easy to implement, and seems to improve the estimation of the gradient. But the paper lacks empirical evidence, in particular consistency of the method over several datasets *with the same setup*.
review_title: null

final_score: rating: 1: strong reject
review_content: summary_of_the_paper: The paper applies the direction derivative to compute the learning problems. 
main_review: The paper is not written well. And the mathematics is not clear. I recommend rejecting this paper. 
summary_of_the_review: The paper discusses the possibility of applying direction derivatives to improve the gradient descent method. There is no concrete calculations and analytical examples to support the idea.
review_title: null

Meta-review: This paper adapts a method called "real-time recurrent learning" for training recurrent neural networks. The idea is to project the true gradient onto a subspace of desired dimensionality along a candidate direction. There are a variety of possible candidates: random directions, backpropagation through time, meta-learning approaches, etc. 

The main strength of the paper is that it is a very simple idea that seems to have practical utility.

While often presented in different contexts, it should be clearly noted by the authors that the general idea of using low dimensional directional derivatives for computational efficiency is fairly common in optimization. Reviewers mention sketch and project methods. This has also been looked, for example, in the context of Bayesian optimization, with [random selection](https://bayesopt.github.io/papers/2016/Ahmed.pdf) and [value of information based](https://proceedings.neurips.cc/paper/2017/file/64a08e5f1e6c39faeb90108c430eb120-Paper.pdf) criteria.


Reviewers appreciated aspects of the paper, though had concerns about relations to sketch and project methods, computational costs, and experimental demonstrations and baselines. Through the rebuttal period, reviewers were mostly satisfied that the concerns about computational costs were well-addressed. A better job could still be done about describing relation to other work. There was also still some desire for more thorough experimental demonstrations and consistent baselines, as described in the reviews. The paper also could use some additional proof-reading as it contains several grammatical errors. On the whole, the paper makes a nice simple practical contribution. Please carefully account for reviewer comments in updated versions.
Decision: Accept (Poster)