Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: Updated review
-----
-----

Given the unanimous support for acceptance amongst the reviewers, I don't think it is really necessary for me to provide a detailed update. The details of how the authors have addressed the concerns expressed in my initial review can be found in the follow up discussion. I now support acceptance without reservation.


Initial review
----
----

# Summary

The authors present a connection between differential dynamic programming (DDP) and back-propagation like gradient descent. The authors use this connection to derive an novel optimizer, DDPNOpt, which combines ideas from DDP to improve the performance with ideas from existing back-prop optimizers, e.g., ADAM, RMSprop, EKFAC, to make the overall approach more tractable. The authors show that this approach is competitive on several benchmarks with a reasonable runtime. Finally, the authors explore the behavior of its regularization term, as well as the effect of vanishing gradients on DDPNOpt.

# Reason for score

Overall, this seems like a good paper and a good first step in this direction. I have a several concerns about the experimental results which justify the lower score, but nothing that would necessarily be a deal-breaker. I would be happy to adjust my score if the authors could clarify some aspects of the experimental results.

# Pros

* The connection between gradient descent and DDP is interesting and, to the best of my knowledge, novel. The resulting approach of adjusting weight updates based on the differential of the hidden states is interesting. I would consider this work likely to generate interest in the community and to inspire follow up work. I'm curious to see if any connections could be drawn with ideas from convex/non-convex optimization in follow-up work.
* The ideas discussed flow well and are easy to follow. It's possible that a reader less familiar with optimal control would have a different experience but I found the arguments convincing with the necessary background concepts properly introduced.
* I found the presentation of alg. 1 and 2 to be insightful. It was useful to include them early in the text and provided something to reference when trying to absorb some of the later points. I caught myself going back to them whenever I had a doubt or question, enough to warrant an acknowledgement.

# Cons

* There are several aspects of the experimental results that raise some questions, but nothing that the authors wouldn't be able to address in their rebuttal. I will be adjusting my review based on the authors response.

# Questions for the authors

* Page 5, curvature approximation section, what does it mean for a layer $f^t$ to be "highly over-parameterized"? Do the authors use this to mean high-dimensional?
* Page 5, curvature approximation section, what is the dimensional of $Q^t_{uu}$? If it is quadratic in the parameters of a single layer, this doesn't seem intractable if materializing the full matrix is avoided, e.g., using a hessian-vector product formulation with a matrix-free linear solvers. Have the authors tried this?
* What are the standard deviations for the results in table 3?
* In figure 3, why does ADAM run faster when batch size is increased (up to 100)? Similarly, why is EKFAC's runtime mostly invariant to batch size? Were these also averaged over 10 runs? Some details about the implementation and how these were measured would help.
* What is the steepest slope for the memory usage of DDPNOpt in figure 3?
* How do ADAM, EKFAC and E-MSA keep a constant memory usage as the batch size increases?
* In table 4, where does the quadratic exponent of $X$ come from in ADAM's memory complexity? How does ADAM's memory complexity avoid a dependency on the batch size?
* Figure 4, what does the value of the $V_{xx}$ regularization axis correspond to?
* Figure 4a, how much of this is DDPNOpt doing better vs the comparison doing worse for certain learning rates? Can the authors show us what these plots would look like compared to the baseline using its best learning rate (or show two sets of plots one with the absolute performance of DDPNOpt and one with the absolute performance of the baseline)?
* Figure 4b, why use lr=0.01, Vxx=1e-5 for RMSprop instead of the seemingly favorable lr=0.045, Vxx=1e-9 (according to figure 4a)?
* Figure 5, it's not quite clear from the supporting text how exactly this figure was generated. Although I understand the high-level idea, I'm not sure I would know how to reproduce it exactly. Can the authors provide some more details concerning how the matrix whose eigenvector is being computed was constructed?
* Page 8, why change the loss function here? This makes it hard to relate these results with the ones discussed earlier. What do these results look like when using the same loss as what was used in table 3 (which I assume was CE)?
* How would the behavior of DDPNOpt (using 2nd order terms) be affected by using activations that have zero 2nd derivatives, e.g., ReLu?

# Minor comments and typos

* I think that, in its current state, figure 1 does more harm than good and could probably be omitted. This figure is dense in details and notation that isn't formally defined until much later in the paper which is likely to frustrate readers as they try to parse the figure while only half way through the introduction. Additionally, even now that I understand each of the terms involved, it's still not quite clear what the figure is meant to convey. Why does the weight update diagram not return new weights (or involve the weights at all)? Why are unused arrows faded in the weight updates for back prop but omitted from the backwards pass? Why does the backwards pass for DDPNOpt not show how all the necessary quantities needed for the weight updates are computed? The other side-by-side comparisons (alg. 1/2, table 2) do a good job at highlighting the similarities and differences between the different settings.
* Page 2, footnote, "given a time-dependent functional $\mathcal{F}_t(x_t, u_t)$ [...] as  $\nabla_x \mathcal{F}_t \equiv \mathcal{F}^t_x$ [...]", this is admittedly a  bit pedantic but as stated here, there are no variable $x$ to differentiate. I would recommend either using $\mathcal{F}_t(x, u)$, or $\nabla _{x_t} \mathcal{F}_t$
* Page 3, explicitly specifying where each derivative function is evaluated would help avoid confusion. Given the previous notation footnote, I would expect terms of the form $\mathcal{F}^t_x$ to be a function, but, as I understand it, they represent the derivatives evaluated at some point.
* Nitpick: how is the product between a vector and a 3D tensor defined? I know what the authors mean but not all readers might be comfortable with this notation. A few words mentioning it's a contraction on one dimension, or, preferably, a formal definition would help those readers (placing this in the appendix would be fine if space is limited).
* "by orders." This is used a few times without specifying what orders are being referred to. When discussing complexity, I have never seen this term used without being accompanied by "of magnitude". I don't believe it is correct to omit these words. If this is common in some literature that I am unfamiliar with, I would appreciate if the authors would let me know.
* There were a few other instances of typos and missing words which I now regret not writing down... In any case, it would be a good idea to carefully proof read the final draft before its eventual publication so that they can be found and corrected.
review_title: Review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper draws connections between training neural networks, and trajectory optimization via differentiable dynamic programming (DDP) from optimal control.

The central idea is to think about the propagation of inputs through a deep neural network as a dynamical system, where the inputs/activations are the signal being propagated, and the weights of the network are control inputs that influence the trajectory of the activations through the network. From this perspective, training the neural network is like trying to control the trajectory (hence, trajectory optimization).

The paper does a good job of presenting this connection, with helpful figures and text to aid the reader.

Given these connections, the paper then goes on to draw explicit connections between trajectory optimization using differentiable dynamic programming (DDP), and standard optimization algorithms for training neural networks (e.g. gradient descent or even approximate 2nd order methods such as KFAC).

The crux of the algorithm is similar to backpropagation in that it involves forward and backward passes, but different quantities are computed for the backward pass. While this seems like a straightforward application of known techniques from control theory to deep learning, the paper does a good job of highlighting similarities and differences to backprop.

The paper tests the proposed algorithm on a handful of classification tasks. My main concerns are with the experiments, I think they could be more thorough and more clearly show the purported benefits of the DDPNOpt algorithm.

First, the paper claims that the DDPNOpt algorithm is more robust. Robust to what? Stochastic gradients? Larger step sizes in the optimization algorithm? I think the paper could do a better job of stating how the DDPNOpt algorithm is more robust, and providence direct evidence demonstrating that. As far as I can tell, the only evidence presented for robustness is the toy illustration in Fig 2.

Second, as the DDPNOpt algorithm optimizes the same total objective as the baseline optimizers, I would expect them to (eventually) reach the same loss. Is this correct? If so, why report just the final accuracies in Table 3? It seems more pertinent to show the entire training trajectory for these problems.

Third, for the vanishing gradients experiment, it is hard to tell if the reason the other algorithms perform poorly is strictly due to vanishing gradients. How are the step sizes for each algorithm tuned? Are the other optimizers stuck at a saddle point? Does the stark difference in performance go away if one were to switch to using ReLU activations, which presumably do not suffer from vanishing gradients as much?

Overall, I think the connections drawn between optimal control and neural network training are themselves interesting and thought provoking, even with my caveats about the experiments.
review_title: Interesting connections between trajectory optimization and training deep networks

final_score: rating: 7: Good paper, accept
review_content: This paper presents a novel alternative to SGD based on Differential Dynamic Programming that views deep networks as dynamical systems. I am very pleased with this contribution and I propose an accept. Some feedback below to further improve the work. 

Positives:
1) The method seems to mitigate the effect of vanishing gradients 
2) Learns models that can outperform state of the art optimizers as well as other methods based on the same family of approximate DP. 
3) The method seems simple to implement and generalizes commonly used ones depending on the choice of Hessian approximation.
4) Despite approximations, the approach is more principled then most SOTA heuristics 
5) The effect of state (hidden activations or pre-activations) feedback on vanishing is illustrated very nicely and experiments are neat. 

Negatives:
1) Approximations come too much sparsely in the paper. Perhaps they should be stated clearly in the initial sections  - possibly not in full technical extent but to give an idea of the key elements that enable the technology to be used. A reader can get scared away by the amount of second order terms that you later discard. The regularization bit on V seems also quite fundamental and its role is often downplayed in papers about DDP. It should also be clear that these steps are needed to use the method. 

2) It is not clear if in the end the method is still second order, considered the amount of approximation taken. This is perhaps a technical detail but it would be nice to clarify further when comparing to Newton for instance.  

3) It is not clear which equations you implement in the final algorithm. In paticular, on page 6 just above Experiment there's a paragraph about `implementation details`  they do not seem to be details really. For instance, you discard some terms in eq (3) so it might be worth highlighting the ones you use directly there, if you don't want to rewrite the full equation. 

My initial score is positive but I think this feedback should be accounted for the revised version and amendements are made to maintain this score.
review_title: Nice work!

final_score: rating: 7: Good paper, accept
review_content: 
A. Summary:
This paper proposes a second-order optimizer, DDP-NOpt, for neural network training. This optimizer views neural networks as a discrete-time non-linear dynamic system and derives an efficient optimizer from differential dynamic programming.
Besides, this paper also connects the existing back-propagation with gradient descent to the DDP framework and explains why the proposed optimizer is better than others under the DDP framework.
Finally, the experiments demonstrate that the proposed method is superior to the other optimal control inspired method and second-order method, as well as competitive with the standard first-order method.

B. Strength:
1. This paper gives a clear discussion about the difference between the proposed method and previous works, which motivates the author to explore the optimizer in the line of approximate dynamic programming, specifically differential dynamic programming.
2. The paper gives sufficient background to help the readers to understand the idea of viewing networks as non-linear dynamic systems and optimize it with differential dynamic programming. It also establishes the connection between existing first-order and second-order optimizer to the DDP framework and gives a clear explanation about why the proposed method is superior in section.3.
3. The experiments are comprehensive. Besides the model accuracy, it also compares the sensitivity to hyperparameters of different optimizers, which is intuitive via visualization. Training a relatively deep network with sigmoid activation also proves the superiority of the algorithm over existing methods.

C. Weakness:
1. There are two sets of terminology through this paper, one is for optimal control, and the other is for deep learning, which is more familiar to me. When reading the section.4, I have to turn back to the section.2 frequently to double confirm the terms. So is that possible to introduce the DDPNOpt right after the DDP, when the reader's memory about the DDP is still fresh? After the DDPNOpt, then we can discuss the connection between BP+GD with DDP, as well as the relation of DDPNOpt with other optimizers.
2. The network structures used in the experiments are not clarified. Different Network structures lead to different dynamics and objective landscape, which may affect the relative effectiveness of the proposed optimizer. For example, it is well-known that networks with residual connection (resnet, densenet) are easier to optimize than the ones without residual connections.  So it would be good if the author could clarify the specific network structure they are experimenting with and demonstrate the generality of the optimizer on different structures.  
4. Does the SGD in the experiment have momentum? If not, it is better to compare with SGD+momentum since it is a more popular choice than vanilla SGD.
5. The analysis in the paper is based on the full-batch case. How the relative performance varies according to the batch size? Only runtime comparison contains the results for different batch sizes. 

D. Justification of the score:
I am not an expert on this topic, so I made the voting from the perspective of a broader audience of the ICLR community. In general, it is a good paper in terms of the novelty and the algorithm. There are some paper organization issues making the paper a little bit difficult to follow, but these issues are fixable, and the paper will be more friendly to a broader audience after this.

E. Expectation for the rebuttal:
I hope the authors could address my questions in C.weakness and make the paper easier to follow for a broader audience.


review_title: A novel optimal control based optimizer with interesting connections to existing methods

Meta-review: Reviewers agreed that connecting neural networks with dynamical systems to create a new kind of optimizer is an interesting idea. After the authors' improvements, this is a strong submission of wide interest.
Decision: Accept (Spotlight)