Learning by Directional Gradient Descent
Authors: David Silver
Anirudh Goyal
Ivo Danihelka
Matteo Hessel
Hado van Hasselt
Venue: ICLR 2022 Poster (2022)
Keywords: credit assignment
directional derivative
recurrent networks

Abstract: How should state be constructed from a sequence of observations, so as to best achieve some objective? Most deep learning methods update the parameters of the state representation by gradient descent. However, no prior method for computing the gradient is fully satisfactory, for example consuming too much memory, introducing too much variance, or adding too much bias. In this work, we propose a new learning algorithm that addresses these limitations. The basic idea is to update the parameters of the representation by using the directional derivative along a candidate direction, a quantity that may be computed online with the same computational cost as the representation itself. We consider several different choices of candidate direction, including random selection and approximations to the true gradient, and investigate their performance on several synthetic tasks.  


Published as a conference paper at ICLR 2022
LEARNING BY DIRECTIONAL GRADIENT DESCENT
David Silver Anirudh Goyal', Ivo Danihelka" Matteo Hessel', Hado van Hasselt
ABSTRACT
How should state be constructed from a sequence of observations, so as to best achieve some objective? Most deep learning methods update the parameters of the state representation by gradient descent. However, no prior method for computing the gradient is fully satisfactory, for example consuming too much memory, introducing too much variance, adding too much bias. In this work, we propose a new learning algorithm that addresses these limitations. The basic idea is to update the parameters of the representation by using the directional derivative along a candidate direction, a quantity that may computed online with the same computational cost the representation itself. We consider several different choices of candidate direction, including random selection and approximations to the true gradient, and investigate their performance on several synthetic tasks.
INTRODUCTION
key requirement of intelligence is the ability to integrate information over time, by constructing an internal representation of state from sequences of observations. This is critical for agent predict or control its future experience, whenever its environment is not fully observable (i.c. whenever individual observation are not sufficient for making the required predictions, or decisions). An efficient representation must construct state incrementally through an update function 8t+1 = pedate(s,, o,) with the previous state 8, and the last observation or as inputs. Since observations may include lots of redundant or irrelevant information, state representations must be tailored to a given task, encoding all and only the aspects of past experience required perform such task.
To learn state representations from data, it is useful to be able to assess how changing the update te function affects the long term performance of the agent. If the update function is parameterized by a differentiable function such as recurrent neural network, we can measure the effect of changing each parameter in terms of a suitable loss function, and then update the parameter in the direction of steepest descent of the loss function, by using a suitable variant of (stochastic) gradient descent. Unfortunately, no existing method for computing the steepest descent direction of recurrent function satisfies all the basic desiderata for a general approach to the problem. Prior methods either use too much memory (BPTT, Rumelhart al. 1986 WWrbos 1988), much computation (RTRL, Williams & Zipser 1989). have too much variance (UORO. Tallec & Ollivier 2017; SPSA, SSall et al. 1992), or too much bias (DPG, Silver et al. 2014 synthetic gradients, Jaderberg
(017b))
In this paper we propose an algorithm to efficiently perform near-steepest descent of recurrent functions, using the same computational and memory complexity as the forward computation of the recurrent function. The proposed approach is based upon the observation that the directional derivative of recurrent function along any arbitrary direction can be computed efficiently and then can be used to construct a descent direction. When applied to recurrent networks, this observation allows the directional derivative of a recurrent function to be computed efficiently in fully online manner, with computational cost the same as the forward computation of the function.
What direction u is most effective? In the special case where matches the direction of the true gradient, we recover the steepest descent update. This suggests the following algorithm: first approximate the true gradient, and then follow a descent direction along the direction of the estimated gradient, order to reduce the loss. We analyse and evaluate empirically random choices of direction, and also investigate directions based upon several methods of gradient approximation.
DeepMind, London, UK, University College London, Mila, University of Montreal. Corresponding author: a rudhgoya1 191
91 98gma com

---

Published as a conference paper at ICLR 2022
2 METHODS FOR APPROXIMATING THE GRADIENT
In this section, we first give brief overview of common methods for approximating true gradient. Notation. We consider recurrent network represented by a differentiable function (4, f 0t, w.). The recurrent network maintains at each time-step an internal "hidden" state ate of size n, and receives an observation Ot- The recurrent function is parameterized by a vector w of size p. At every time-step there is a loss 4. For our purposes, any output of the network (such as its predictions or actions) may be considered to be part the internal state Iy that leads to a loss 4, The objective is to minimise the total loss I. = Σi= 4 over T time-steps. A key requirement for efficient optimization is the computation of the gradient of the total loss with respect to the parameters. 81. Tu Bu
- al.
(BPTT). Backpropagation-tiee whwprioooooooou-tiiieeet (BPTT) uses backward differentiation compute the gradient of the cumulative loss with respect to the parameters of a recurrent neural network. Specifically, the gradient can be computed by exchanging indices to consider the effect of state 24 all future losses 4, 4,.,,,. I..
0L
0h
04 dz
al
dz
dw
dw
Or, Ow
Ow
The inner term may be accumulated by backpropagation of error,
T
04
04.
T
al, 0r++1
dz
dz
0ze+1 dr.
j=t+1
This requires just (p) computation per time-step; however, the entire sequence must first be processed forward compute the output. In practice, the memiry-requirrmmnts of BPTT limit the computation of gradients to short windows, and limit the choice of neural network architecture to those with modest memory requirements. the gradient of large neural networks must be computed over long horizons then BPTT may not be an appropriate choice of algorithm.
Synthetic Gradients and Direct Policy Gradients. We now consider how one may use ideas drawn from reinforcement learning to estimate the future loss and hence allow for efficient online compu-
tation of gradients. One may estimate the loss using a value function ū(z;) R E/=r's lj and use the estimated loss in place of the true loss,
aL
T
T
al
dr
T
Oū(x2) dz
(2)
Ow
Ox.
Ow
Sx.
Ow
3=1
where the loss may be estimated by bootstrapping from the next time-step, ū(x;) R 4 IJ Ei=+t R3
4 + ((x+11). Alternatvelly, one may estimate the backpropagated gradient i'(xx) ~ ES use the estimated gradient in place of the true gradient,
0l++1
and
da,
àL
dr
('(t))
Dw
Ow
where the backpropagated gradient may be estimated by bootstrapping from the next time-step.
d'(xx) Ry Aie
+ ン5=++1 Dreti
at, 0z.+1
ss öl.
+ (1(++11) 0 dze
O...
It is worth noting that the former approach is equivalent to the Deterministic Policy Gradient (DPG) (iilvrr et al. 2014) in a reinforcement learning problem where the state considered be the input state = -t-1, the action is the next state
the policy is the function mapping from state It-1 action 2; parameterized by weights w, and the reward is the negative loss r; -1e (Jaderberg et al. 2017b).
In practice, both deterministic gradients and synthetic gradients introduce significant bias into the estimate of the gradient. This has the downside that stochastic gradient descent, applied to the estimated gradient, may not actually descend the loss and may fail to converge.
2

---

Published as a conference paper at ICLR 2022
Real-time recurrent learning (RTRL). We now consider methods that compute the gradient of recurrent function by forward differentiation. Given a function 2 = (h (1))..... with derivative da JT....1 where Jt is the Jacobian of function ft, one may instead compute the derivative dy
de
(Jg())) by processing the chain rule in forward direction and caching the intermediate dy
quantity dy
dh J....1. This is only computationally efficient when is smaller than this is the opposite case to usual in deep learning where we have many parameters for and scalar loss for
Real-time recurrent learning (RTRL, Williams & Zipser 1989) applies forward differentiation to compute the gradient of the cumulative loss with respect to the parameters of recurrent functions. This is achieved by caching the sensitivity of state to weights des i.e. the total derivative of state to dw
weights via all previous states,
OL
Ole dw
T
Øle dæ. dx, dw
ow
The sensitivity may be accumulated via forward accumulation,
dx
0ret1
0xe+1 dx dw
dw
dw
dz,
The size of the matrix due is X p and the computational cost of multiplying the Jacobian matrices due the second term is Oppn²), leading to costly overall algorithm that is impractical for large-scale deep learning.
DEEP ONLINE DIRECTIONAL GRADIENT ESTIMATE (DODGE)
After explaining a directional derivative, we will introduce our online directional gradient estimate.
3.1 DIRECTIONAL DERIVATIVE
A basic property of gradients is that the directional derivative can be computed efficiently. One may efficiently compute the Jacobian-vese veecor product dy (J2( u))) for any tangent vector of size p. A geometric interpretation this product is the directional derivative of the gradient, i.e. ds describes how much the gradient descends in the direction of the vector u. dy
3.2 GRADIENT ESTIMATE
When applied to recurrent networks, the directional derivative of recurrent function can be computed efficiently with computational cost just O(p) per time-step, i.e. the same the forward computation of the function.
0L
T
04,
dx dw
Σ Ow
.u)
do:
t=1
dr dw
dz(+1
u 0z4+1
dxr
u
Ow
dx,
dw
For any unitary calculating the directional derivative along that direction provides a valid descent direction for updating weights, Aw x @LL u) u.
The direction of steepest descent may be computed from many such tangent vectors, for example
- De De;e; for the unit bases e,, ..., Ep. This requires p separate directional derivatives. ~ {-1,+1]² may be sampled, leading to an accumulated Dw u;) u4),, but at the cost of introducing significant variance.
Alternatively, random directions such as u;
gradient estimate aL
~ 1 E
0L
Ze
However, if the tangent vector is chosen to be the gradient direction itself, = then only such directional derivative required,
- where at
dw
(g u)u
g
||9||
9
||l||
9-
3

---

Published as a conference paper at ICLR 2022
We often interested in the expectation of the gradient, E [g] rather than the sample gradient. For example, stochastic gradient descent (SGD) averages over sample gradients to descend in the direction of the overall gradient. When using directional gradient descent, one may either compute the directional derivative of an individual sample gradient, and then average, or compute the directional derivative in the direction of the expected gradient
where 9 E [g]. and then average:
9
9
9
9
E [(g uyuu = E
This suggests a novel strategy of estimating the expected gradient and using the estimated gradient as descent direction in & u)u. Note that, regardless of the quality of the gradient estimate, the algorithm will always follow valid descent direction.A valid descent direction has a non-negative dot-product with the true gradient. The quality of the gradient solely determines descent in expectation. In the next section, consider methods that provide such estimate of the gradient. We refer to this family of algorithms as Deep Online Directional Gradient Estimate (DODGE) and they can be understood near-steepest descent algorithms.
steepness of
def dodge loss_function, params, direction): Compute the Jacobian-ves loss, loss_jvp jax jvp (loss_ (loss_function, [params], [direction]) grad_estimate - loss_ivp direction return loss, grad_estimane
product.
Listing I: DODGE implemented in JAX.
3.3 METHODS FOR DODGE
We now consider several possible methods for estimating the expected gradient g. When training on data from stationary distribution, I may be estimated by averaging over many approximate sample gradients E [g]. In the proposed update rule, the DODGE algorithm updates the gradient estimate using a moving average Ağ = a(ğ - g) and update the weights using SGD, Aw -3( The Tell Tell
The sample gradient ğ = aer may be approximated in many ways. We consider several methods:
ORACLE As baseline, the exact sample gradient ğ
TBPTT Truncated Backpropagation Through Time can propose biased gradient ÿ. DODGE is able to convert the biased gradient to a valid descent direction.
DPG The deterministic policy gradient = -T 0ā(wx) âr.
aL
dx.
Dw
SYN The synthetic gradient ğ = ET= ('(x,)
Bz. Al
Bu Dun
The computational cost of the proposed method is double than that of the forward computation of the function i.e., one forward pass for computing the candidate direction, and another forward pass for computing the directional derivative.
Computational cost:
DODGE MATHEMATICAL PROPERTIES
Given a direction u, DODGE estimates the ith element of the gradient by
g(i) u(i) Σ [k(k)g(k).
(3)
We will list several properties of this estimate, with more properties listed in Appendix
4.1 NON-NEGATIVE DOT- PRODUCT.
DODGE has non-negative dot-product with the gradient:
g ((g u)u) g (g u) 0.
(4)
The non-negative dot-product enables that the expected loss is lower after an update with a small enough step size (Bottou al. 2018)
4

---

Published as a conference paper at ICLR 2022
4.2 RANDOM DIRECTIONS
Unbiased estimate with random directions. If the u elements are independent with zero mean and unit variance, then DODGE is unbiased estimate of the gradient:
B [i) E u(i) Σ (k))g(k) =E g + u(i) Σ
En(k)g(k)
E [g(
(5)
Variance with random signs. If each element contains random sign from {-1, 1}, then the variance of (i) is
= = (6 - [o(1)) =3 ( ) -B² [x(
E (0(t)) - E [o(i))
(6)
Σ [g) - E [o(i))
= E ((((1) E [o())) + Σ [g))(()))
(8)
where we used the fact that the variance of sum of independent terms equals a sum of variances. Notably, the variance is proportional to the number of parameters and not affected by the size of the state representation.
4.3 MULTIPLE RANDOM DIRECTIONS
There are two simple approaches to use multiple random directions.
Average of estimates. The first approach would multiple independent random directions and average the obtained estimates of the gradient. If using Nairs directions with random signs and each E [ (k)] is 0², the average of multiple estimates has variance
E (0uvg
E [g)
[(((t) E [[(())]]
P
0² Ndirs
where p the number of parameters.
Direction partitioning. Another approach would be generate one random direction and partition to multiple parts, padded with zeros. The gradient estimate is then obtained by the sum of estimates from the parts. This approach has lower variance compared using the average of the estimates.
using Ndirs parts, each with Nais
P
random signs, this approach has variance
E (Opartitioned (i) E { E (g( [g(1))) p Nairs x²
(10)
Naire
If the number of directions Naiss equal the number of parameters p. each g(i) can be estimated perfectly. In this extreme, each direction is one-hot vector with random sign. We also note that this case can be seen generalisation of RTRL. the case of the number of directions equal the number of parameters (i.e., Nairs p) DODGE would be mathematically equivalent to RTRL.
4.4 GEOMETRIC INTERPRETATION OF DODGE
Consider a set of & orthonormal directions U = [M Ug. For example, in high-dimensional spaces, independent random directions orthoontl with high probability. We project the gradient onto the subspace spanned by those directions, ØL
3L P. SLUUT Σか (o ...) u Ju
ØL This projection is computed online by DODGE from directional derivatives u, Bu at a cost of k times the forward computation. The projected gradient may be used to update parameters, e.g. Aw a 22 ULU which provides descent direction, L(w + Aw) < L(w) for sufficiently small a, with equality only at local minima when the gradient is orthogonal to the subspace.
5

---

Published as a conference paper at ICLR 2022
5 EXPERIMENTS
We now report and discuss the results of an empirical study that analyses the performance of the proposed estimator using different tasks, as well as using different ways to approximate the expected gradient. We use JAX (Bradbury et al., 2018) to implement all experiments. To implement DODGE, need to compute Jacobian vector product, and JAX has excellent support for Jacobian-vector products. We provide an example DODGE implementation in Listing] I
5.1 PROBLEMS
We evaluate the proposed DODGE update on different problems. We first give brief descrip- tion of the different problems and then in the next section we discuss different ways of getting the direction required compute the DODGE update. We now describe the details of our implementation. On sequence modeling tasks, we use an LSTM network (Hochreiter & Schmid- huber, 1997) with 128 units and a batch size of 32. We optimize the log-likelihood using the Adam optimizer (Kingma & Ba 2014). For each method, we choose the best learning rate from (0.003, 0.001, 0.0003, 0.0001, 0.00003, 0.000013. based on the final performance. We repeat each experiment times with 5 different random seeds.
Copy task. The copy problem defined in Graves et al. (2014) is synthetic task designed to test the model's ability to remember a sub-sequence for a large number of time-steps. Here, we would like to test out whether near-steepest descent can help to learn long-term dependencies.
MNIST classification task. It is database of handwritten digits (LeCun 1998) that commonly used for training and evaluating image classification models.
Influence Balancing lask. This task was introduced by Tallec & Ollivier (017)) to study the bias in the gradient estimate from truncated backpropagation through time. This task is particularly sensitive to short-horizon bias, as the gradient for the single parameter 0 E R has the wrong sign when estimated from short unrolls.
Image regression NeRF task. This task trains the initial parameters of 2D-NeRF model (Milden hall al. 2020), represented by an MLP. The network takes in pixel coordinate (z, y). and then outputs the (R2 G. B) color value at the particular position. The learned initial parameters need to support fast adaptation for each new image. We build upon the experimental setup proposed by Tancik et al. (2021).
5.2 SANITY CHECK
Table 1:
Influence balancing task: TBPTT with a short truncation length di- verges, while DODGE with random direc- tion performs exactly the same as RTRL.
We empirically show that for a model with a single pa- rameter, the DODGE update is equivalent to RTRL. In order to explore this we use the influence balancing task. This task involves learning of scalar parameter. We use the same experiment setup as in (Tallec & Ollivier 2017). Since we are training only single parameter, we use a random direction. In Table we empirically show that the implementation of the proposed method achieves exactly the same performance as the exact RTRL.
Method
Loss
TBPTT (truncation length 100)
0.93
RTRL
1.1
DODGE
1.11e-12
5.3 RANDOM DIRECTIONS AS CANDIDATE DIRECTIONS
Increasing the number of random directions helps. We first show that a random direction can be converted to valid descent direction. In order to test this, we train the model using a DODGE update on the MNIST classification task. Figure shows the result of training a model by DODGE with random directions. It also shows that increasing the number of random directions improves the learning speed, but learning is possible and stable even with a single random direction. We also test the use of the random directions the copy task. Figure shows DODGE on the copy task. There, DODGE with random directions achieves low loss only when using 64 random directions, which may not be feasible for networks with many parameters.

---

Published as a conference paper at ICLR 2022
1.0
1.0
1.0
0.8
0.9
0.8
train. acc
train acc
train, aacc
0.6
0.6
0.8
D=1
D=1
D=3
D=3
T=1K
0.4
0.4
D=10
0.7
D=10
T=2K
D=30
D=30
T=3K
0.2
D=100
D=100
0.2
T=4K
oracle
0.6
oracle
oracle
0.0
0
2000
4000
100
500
1000
200
400
step
batch_ size
mlp_size
a)
b)
c)
Figure 1: Training accuracy MNIST for feedforward neural networks trained by DODGE with random directions. a) We report the accuracy as a function of the number of updates. In grey, DODGE with oracle steepest descent directions. From orange to dark blue, DODGE with increasing numbers of directions sampled on each update, from directions improves performance, but learning is possible and stable even with single direction. b) parameter study of the joint effect of the number of directions and the batch size used to evaluate the directional derivative along each direction. We evaluate the accuracy after seeing a fixed number of samples (regardless of how they are batched). Increasing batch size from 100 to 300 improves performance, especially when using single direction (in orange). Increasing the batch size further (to 1000) however decreases performance. <) A parameter study of the effectiveness of DODGE for different network sizes. The accuracy is reported as function of the number of units in the two hidden layers of the multi-layer perceptron used in the experiment. The different lines correspond to different snapshots during training: after 1000, 2000, 3000, 4000 updates, respectively.
100. Estimating the gradient using more
5.4 APPROXIMATE CANDIDATE DIRECTIONS: TBPTT, REPTILE, AND SYNTHETIC GRADIENTS
As discussed in Section 3.3 there are various ways to approximate the true gradient. For example, one can approximate the true gradient either via the use of truncated backprop. which reduces memory consumption at the cost of increasing bias, or the use of first-order algorithms for meta-learning that do not differentiate through the inner loop, or by learning a critic that estimate the true loss and its gradient. Here explore using these different methods for estimating the expected gradient, and then using the estimated gradient as a candidate direction for computing the directional derivative.
5.4.1 DIRECTION A RESULT TRUNCATED BACKPROPAGATION
In order to evaluate whether the DODGE update can help in learning long term dependencies we evaluate DODGE on the copy task. For all our experiments, we use sequence of length 25. Truncated backpropagration through time (TBPTT) for training recurrent networks known to have trouble remembering inputs has seen many steps ago. In order to get the direction used for calculating the DODGE update, we randomize the truncation length across different batches by uniformly sampling the truncation length from f1.... ......,,ax.. max_ trunc len) Taalec & Ollivier (2017) used importance sampling to unbias the truncated gradients and required a longer maximum truncation length. Figure shows the results of using direction from TBPTT to compute DODGE update.
The four different plots are for different truncation lengths. The DODGE update helps mainly on short truncation lengths (max_trune trunc len
5.4.2 DIRECTION AS A RESULT OF REPTILE.
Meta-learning seeks to learn a network that can adapt quickly on previously unseen task. Model- Agnostic Meta-Learning (MAML, Finn et al., 2017) uses an outer loop of gradient based learning to learn highly adaptive initial parameters. The algorithm unrolls in the inner loop and differentiates through the resulting computation graph. Alternatively, Reptile (Nichol et al. 2018) updates the initial parameters towards the final parameters learned task. Because Reptile does not backpropagate through the inner loop of the computational graph, Reptile saves memory at the cost of obtaining biased gradient estimates.
7

---

Published as a conference paper at ICLR 2022
Copy Lask max truc.leeeee Jen
Copy lesk max, max_truc Jenie
Copy task max, tru, len=00
Copy task max, max_truc_eeee Iruc_len=13
TBPTT
30
0.4
0.3
0.2
0.3
0.0
250
150
Thousands
Thousens
Thousands
Thousands training
Figure 2: DODGE with a direction from truncated backpropagation through time (TBPTT). We plot cross-entropy (Y axis) as function the training steps (X axis). Lower cross-entropy is better. Shades denote standard errors from 5 seeds.
NeRF task
NoRF task
28
26
24
22
20
18
2
DODGE 3nner_mepss RepCle stopses
Roptie staps=2
16
Thousonds
Thousands training
Figure 3: Direction from the update proposed by Reptile. DODGE as result of using direction proposed by Reptile. We plot Peak Signal-to-Non -o-ise Ratio (PSNR; Y axis) as function of the training- steps (X axis). Higher PSNR is better. PSNR is commonly used to quantify the reconstruction quality for images.
Figure 3 shows the experimental results on the image regression NeRF task with CelebA images Liu et al. 2015). For DODGE, we use as the direction the update proposed by Reptile. The figure shows that the network optimized by DODGE learns faster, especially in the setting with two inner steps.
5.4.3
DIRECTION AS A RESULT OF LEARNING CRITIC: SYNTHETIC GRADIENT.
Copy task
DODGE Copy task
Copy task
BPTT
synthetic grads
0.5
DODGE random
Do0GE nendom langer
0.3
0.2
50
100
150 braiing stops
125
175
50 1.0
125
150 175
Thousands training stops
Thousands
Thousands training staps
(b)
Figure 4: We plot cross-entropy (Y axis) function of training-steps (X axis) on the copy task. Lower cross-entropy is better. (a) DODGE using an oracle direction (i.e., the gradient computed by BPTT the previous minibatch). (b) DODGE using multiple random directions. Multiple random directions reduce the variance and allow to use larger learning rate. (c) DODGE using a direction proposed by critic (learned using synthetic gradients).
We now consider ideas from reinforcement learning which allows one to estimate the future loss by learning value function and then using the estimated loss in place of the true loss. We use synthetic
8

---

Published as a conference paper at ICLR 2022
gradients for learning the critic proposed by Jaderberg et al. 20). For analyzing the DODGE update using synthetic gradients, we use the copy task of length 25 as in the case TBPTT.
Figure 4 shows the cross entropy values plotted against the number of training steps using the DODGE update compared the synthetic gradient baseline. Here also the network trained with the DODGE update optimizes faster as compared to the baseline.
RELATED WORK
Online credit assignment in RNNs without backtracking remains an open research problem. RTRL (Williams & Zipser 1989) attempts to solve this problem by estimating gradients using forward mode automatic differentiation instead of backpropagation. Forward mode automatic differentiation allows for computing unbiased gradient estimates in an online fashion, however, it normally requires storage of the gradient of the current hidden state values with respect the parameters, which is ((N3) where N is the number of hidden units. The Unbiased Online Recurrent Optimization (UORO) (Tallec & Ollivier 2017) method gets around this by updating rank-1 approximation, which is shown to keep the estimate of the gradient unbiased, but at the cost of increasing the variance of the gradient estimator. DODGE with random signs can also benefit from the variance reduction method proposed in UORO, by rescaling the random signs (if we know the variance of the gradient elements). Various approaches use sparse approximations for real time recurrent learning, like SnAp (Menick al. 2020), which provides deterministic biased gradient and can be combined with DODGE (by using SnAp to provide a candidate direction). Optimal Kronecker- (OK, Benzing et al., 2019) is designed for specific network architecture and achieves low variance at a higher computation cost than UORO. Interestingly, DODGE with a random direction can be seen as an unexplored special case of the generalized UORO estimator by Cooijmans & Martens (2019). More recently. |Violl et al. (202T) introduced Persistent Evolution Strategies (PES), a method for unbiased gradient estimation by estimating gradients from truncated unrolls and allowing frequent parameter updates. On the influence balancing task, DODGE with one random direction reproduces RTRL, while PES requires 10 particles.
Approximation
Previously, directional derivatives were successfully used for Bayesian optimization with a random direction (Ahmed et al. 2016) or with a direction based on the value of information (Wu et al.) 2017). The proposed estimator is also related to the "sketch and project" gradient estimate (Hanzely et al. 2018). which uses a sketch to construct an unbiased estimator of the gradient. With DODGE, we consider adaptive estimates of the true gradient to provide candidate direction (i.e., to construct the sketch). To the best of our knowledge, these methods have not been studied specifically in the context of dynamic models (i.e., training of the recurrent architectures).
CONCLUSION, LIMITATIONS AND FUTURE WORK.
Conclusion. In this work, we proposed the idea of using a directional derivative to compute the descent direction for updating the parameters of a neural network. We analyzed different ways to get candidate directions, including random selection and estimating directions that may be close to the true gradient. The proposed learning algorithm computes the directional derivative along descent direction which is then used to update parameters. We empirically showed that the DODGE update helps to improve the convergence when gradient is approximated through different choices of candidate direction. We also showed that multiple random directions can be combined to reduce the variance.
Limitations and Future Work. Here, we focus on building a strong foundation by carefully analyzing the proposed estimator in various different scenarios (i.c., different approximations to true gradient). limitation of the current study is that we don't evaluate on problems where the credit needs to be assigned to states or actions which may be separated by thousands of time-steps like often the case for problems in reinforcement learning. Another limitation that for the problems involving approximate candidate directions we limit our simulations to the scenario where we only use single direction as compared to either using multiple directions at a particular time-step or by changing the directions in online fashion. Our experiments with random directions show that using multiple random directions improves the convergence. Future work would investigate using multiple approximate candidate directions for updating parameters.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We would like to thank Charles Blundell and Fabio Viola for helpful advice and help with experiments.
ETHICS STATEMENT
The authors do not foresee any negative social impacts of this work, but of course the accumulation of improvements in ML could misused as may give more power to nefarious agents.
REFERENCES
Mohamed Osama Ahmed, Bobak Shahriari, and Mark Schmidt. Do we need "harmless" bayesian optimization and "first-order" bayesian optimization? NIPS BayesOpt. 2016.
Frederik Benzing, Marcelo Matheus Gauy, Asier Mujika, Anders Martinsson, and Angelika Steger. Optimal Kronecker-sum approximation of real time recurrent learning, In Proceedings of the 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pp. 604 613. PMLR, 09-15 Jun 2019.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3) -31 2018.
James Bradbury. Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Miine and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http://githie thub..
com/ wwt. gomp//ooll///1/ jax
Tim Cooijmans and James Martens. On the variance of unbiased online recurrent optimization. arXiv preprint 1XXXv:1902.0240: 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of
deep networks. International Conference on Machine Learning, pp. 1126-1133 PMLR, 2017.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv:1410.5401, 2014.
arXiv preprint
Filip Hanzely, Konstantin Mishchenko, and Peter Richtarik. SEGA: sketching. In Advances in Neural Information Processing Systems, volume 31, 2018.
Variance reduction via gradient
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735-1780, 1997.
Max Jaderberg, Wojciech Marian Czarnecki, Simon Osindero, Oriol Vinyals, Alex Graves, David Silver, and Koray Kavukcuoglu. Decoupled neural interfaces using synthetic gradients. In International Conference Machine Learning, pp. 1627-1635, PMLR, 2017a.
Max Jaderberg, Volodymyr Mnih, Wojciech Marian Czarnecki, Tom Schaul, Joel Z Leibo, David Silver, and Koray Kavukcuoglu. Reinforcement learning with unsupervised auxiliary tasks. In International Conference on Learning Representations, 2017b.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 141.vv1412.6980 2014.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Jacob Menick, Erich Elsen, Utku Evci, Simon Osindero, Karen Simonyan, and Alex Graves. A Practi- cal Sparse Approximation for Real Time Recurrent Learning. arXiv e-prints, art. arXiv:2006.07232. June 2020.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. In European conference on computer vision, pp. 405-421. Springer, 2020.
10

---

Published as a conference paper at ICLR 2022
Alex Nichol, Joshua Achiam, and John Schulman. On First-Order Meta-Learning Algorithms. arXiv e-prints, art, 1.XXv:1803.029900 March 2018.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning internal representations by error propagation. In Parallel Distributed Processing, volume I, pp. 318-362. MIT Press, 1986.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. International Conference on Machine Learning, pp. 387-395. JMg,. 2014.
James C Spall et al. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE transactions on automatic control, 37(3):332-33 -332111,,, 1992.
Corentin Tallec and Yann Ollivier. Unbiased online recurrent optimization. arXiv preprint 170.000700.0 2017.
Matthew Tancik, Ben Mildenhall, Terrance Wang, Divi Schmidt, Pratul P Srinivasan, Jonathan T Barron, and Ren Ng. Learned initializations for optimizing coordinate-basse based neural representations. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2846-2855, 2021.
Paul Vicol, Luke Metz, and Jascha Sohl-Dickstein. Unbiased gradient estimation in unrolled computation graphs with persistent evolution strategies. In International Conference Machine Learning, pp. 10553-10563. PMLR, 2021.
Werbos. Generalization of backpropagation with application to a recurrent gas market model. Neural Networks, 1, 1988.
Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-280, 1989.
Jian Wu, Matthias Poloczek, Andrew G Wilson, and Peter Frazier. Bayesian optimization with gradients. In Advances in Neural Information Processing Systems, volume 30, 2017.
A ADDITIONAL DODGE MATHEMATICAL PROPERTIES
Given a direction u, DODGE provides the following estimate of the gradient:
g = (g u)u.
(1I)
We will list more properties of this estimate.
A direction can recover the expected Adam's update. We need to be careful when using DODGE with an advanced optimizer. Many optimizers assume that the gradient estimate is unbiased. For example, if combining non-random DODGE with Adam (Kingma & Ba 2014), we would not have non-negative dot-product of the Adam's 's update with the expected gradient. The product of Adam's 's
diagonal matrix and DODGE's wur" matrix is not always positive definite matrix. We can instead incorporate Adam 's scaling inside the direction u.
Given a scale c(i) > 0 for each gradient element, we want to obtain c(t) [g(1). If u(i) = c(i)Bla(() the expected estimate becomes the wanted quantity: v VE, ([6))")(()]]
[g()]
u(1) Σ ((k)g(()) = c(i)E(g(()
(12)
A.1 RANDOM DIRECTIONS WITH BASELINE
Unbiased estimate with a baseline. We will mention the possibility to combine DODGE with a baseline. Let define DODGE with baseline
(1) = u(i) Σ u(k)g(k) u(1) Σ u(k)b(k),
(13)
11

---

Published as a conference paper at ICLR 2022
where b(k) is the k-th element of the baseline b IP. If he u elements independent with zero mean and unit variance and if b(k) is independent of u(k), then ukk)b(k) has zero mean and g(i) is an unbiased estimate of g()).
Variance with random signs and a baseline. b is independent of and each element contains a random sign from {-1, 1. then the variance of (i) is
E (1) E [x()))
E
(1) - E² [o())]
(14)
E
g(i) + u(i) Σ (b)(((())))) - b(A))) -b(()))))(0)))))))))
E [o(t)]
(15)
Righs
E [(((t) E (o())))
- (()(k))b(b))) b({)))
(16)
The g would be the perfect baseline. Unfortunately, the perfect baseline is hard to obtain.
A.2 HYPER-PARAMETERS.
Nerf task. We build upon the experimental setup as proposed by Tancik al. (2021)
Copy Problem. On sequence modeling tasks, we use an LSTM network (Hochreiter & Schmid huber 1997) with 128 units and a batch size of 32. We optimize the log-likelihood using the Adam optimizer (Kingma Ba 2014). For each method, we choose the best learning rate from {0.003, 0.001, 0.0003, 0.0001, 0.00003, 0.00001 }. based on the final performance. We repeat each experiment times with 5 different random sceds.
For experiments using direction as a result of learning a critic (synthetic gradient), we train for 200K gradient steps with batch size of 32. To train the critic use truncation length of 5, and syngrad scale of 0.5, and we use quadratic critic as recommended in (Jaderberg et al. 2017b).
12


Reviews:
[{"review_id": "kjmjE0PE6wV", "reviewer": "Reviewer_AjYD", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is not written well. And the mathematics is not clear. I recommend rejecting this paper. ", "summary_of_the_paper": "The paper applies the direction derivative to compute the learning problems. ", "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.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HTkTgsSuRXy", "reviewer": "Reviewer_gsh8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n- 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.\n\n- The paper has empirical evidence that the proposed method works across a range of gradient estimators from BPTT, Reptile etc.\n\nWeaknesses:\n\n- 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. \n\nI 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.\n\n- 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.\n\n- 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?\n\n- 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. \n", "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).", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5_dwU2ISSh", "reviewer": "Reviewer_brku", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Preliminary remarks\n\nThe 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.\n\nSo, despite its simplicity, \"DODGE\" seems to be quite new. However, I might have missed some references.\n\nReference about \"random coordinate descent\", close to the main idea of the paper : *Langevin Monte Carlo: random coordinate descent and variance reduction*, Ding 2021.\n\n# Strengths\n\nThe 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). \n\n# Weaknesses\n\nThe 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).\n\n# Clarity\n\nOverall, the paper is easy to follow. However:\n * there are many typos (see below);\n * 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);\n * 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.\n\n# Typos\n\n* p 3: \"for any $u$\" => \"for any unitary $u$\"\n* p 4: in the code excerpt: \"gradient_estimate\" becomes \"grad_estimate\"\n* p 4: \"ORACLE\": bad alignment\n* end of p 5: \"<=\" => \"$\\leq$\"\n* p 6, Sec. 5.2: \"RTRL\": bad alignment\n* p 8: fig. 2: titles: \"max_truc_len\" => \"max_trunc_len\"", "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$.\n\nNotably, this method can be used in two ways:\n * estimating the true gradient by computing its projection on a random low-dimensional subspace of the parameters;\n * 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}$.", "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*. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3yWlBuYrpsr", "reviewer": "Reviewer_GYWv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea is simple and intuitive: Any vector $u$ can be turned into a\ndescent direction by computing\n$\\langle \\nabla L(w), u \\rangle u$, where the inner product may be obtained at a lower cost than computing\nthe gradient $\\nabla L(w)$ itself.\n\nThis idea has been known in the optimization literature as a \"sketch and\nproject\" gradient estimate (see, e.g., [1] and citations therein).\nThis line of work should be cited and duly acknowledged.\nTo my knowledge, it hasn't been studied specifically in the context of\nrecurrent ML architectures, so a paper like the present one could still have its merits.\n\nThe computational cost of the proposed approach is not discussed in \nsufficient detail. \nWhile the memory savings compared to (T)BPTT\nare apparent, I don't see a reason why the *computational* complexity would\nbe any lower. \nWe are still relying on a gradient computation of $\\frac{dx_t}{dw}$, even if \nwe immediately project that partial derivative onto the candidate direction.\nUnless I am missing something, this cost is *added* to the cost of computing\nthe candidate direction.\nThat means that using directional gradient trick in conjunction with a candidate\ndirection based on TBPTT/DPG/SYN would (at least) double the computational\ncost. Could the authors please clarify this aspect?\n\nThe experimental comparison is a bit lacking in my opinion. \nOn every problem, only one competing method is compared to. Why not report\nthe performance of all baseline methods for each test problem?\n\nExcept for the lacking discussion of computational cost, the paper is clear and well-written.\n\n\n[1] https://proceedings.neurips.cc/paper/2018/file/fc2c7c47b918d0c2d792a719dfb602ef-Paper.pdf", "summary_of_the_paper": "The paper proposes directional gradient descent as a way to approximate \nthe gradient in recurrent learning. Directional gradient descent\nuses a candidate direction (e.g., a random vector or a biased gradient\nestimate) and then \"corrects\" that estimate by scaling it with the\ndirectional derivative, i.e, the inner product between the candidate \ndirection and the true gradient (or an unbiased estimate thereof).", "summary_of_the_review": "Essentially, the paper is applying the known \"sketch and project\" trick\nto recurrent learning, so the novelty is rather limited. The experimental\ncomparison is a bit lacking in my opinion and there is a big question mark in terms of the added computational cost\n(and whether that is worth it in practice). I am recommending rejection\nfor now, but would encourage the authors to respond to my concerns in the rebuttal.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)