DDPNOpt: Differential Dynamic Programming Neural Optimizer
Authors: Guan-Horng Liu
Tianrong Chen
Evangelos Theodorou
Venue: ICLR 2021 Spotlight (2021)
Keywords: deep learning training
optimal control
trajectory optimization
differential dynamica programming

Abstract: Interpretation of Deep Neural Networks (DNNs) training as an optimal control problem with nonlinear dynamical systems has received considerable attention recently, yet the algorithmic development remains relatively limited. In this work, we make an attempt along this line by reformulating the training procedure from the trajectory optimization perspective. We first show that most widely-used algorithms for training DNNs can be linked to the Differential Dynamic Programming (DDP), a celebrated second-order method rooted in the Approximate Dynamic Programming. In this vein, we propose a new class of optimizer, DDP Neural Optimizer (DDPNOpt), for training feedforward and convolution networks. DDPNOpt features layer-wise feedback policies which improve convergence and reduce sensitivity to hyper-parameter over existing methods. It outperforms other optimal-control inspired training methods in both convergence and complexity, and is competitive against state-of-the-art first and second order methods. We also observe DDPNOpt has surprising benefit in preventing gradient vanishing. Our work opens up new avenues for principled algorithmic design built upon the optimal control theory.

Published as a conference paper at ICLR 2021
DDPNOPT: DIFFERENTIAL DYNAMIC PROGRAMMING NEURAL OPTIMIZER
Guan-Horng Liu' Tianrong Chen', and Evangelos A. Theodorou' 'Center for Machine Learning, "School of Aerospace Engineering, Sccoool of Electrical and Computer Engineering, Georgia Institute of Technology, USA [ghliu, tianrong. chen, evangel thwodorou @ gattech. edu
ABSTRACT
Interpretation of Deep Neural Networks (DNNs) training as an optimal control problem with nonlinear dynamical systems has received considerable attention recently, yet the algorithmic development remains relatively limited. In this work, we make an attempt along this line by reformulating the training procedure from the trajectory optimization perspective. We first show that most widely-used algorithms for training DNNs can be linked to the Differential Dynamic Programming (DDP), a celebrated second-order method rooted in the Approximate Dynamic Programming. In this vein, we propose a new class of optimizer, DDP Neural Optimizer (DDP- NOpt), for training feedforward and convolution networks. DDPNOpt features layer-wise feedback policies which improve convergence and reduce sensitivity syper-parametee over existing methods. It outperforms other optimal-contre inspired training methods in both convergence and complexity, and is competitive against state-of-the-an first and second order methods. We also observe DDPNOpt has surprising benefit in preventing gradient vanishing. Our work opens up new avenues for principled algorithmic design built upon the optimal control theory.
INTRODUCTION
In this work, we consider the following optimal control problem (OCP) in the discrete-time setting:
T
min J(ū; (0) = (((TT) ) + Σ la u.)
s.t. 01+1 = fe(We, us))
(OCP)
2=
where H2 E Rn and u, E RT represent the state and control at each time step t. f((; :), le(. and ((.) respectively denote the nonlinear dynamics, intermediate cost and terminal cost functions. OCP aims to find control trajectory, A {u, [T= such that the accumulated cost J over the finite horizon E {0, 1, T is minimized. Problems with the form of OCP appear in multidisciplinary areas since it describes generic multi-stage decision making problem (Gamkrelidze, 2013), and have gained commensurate interest recently in deep learning (Weinan, 2017; Liu & Theodorou, 2019).
Central the research along this line is the interpretation of DNNs as discrete-time nonlinear dynamical systems, where each layer is viewed as distinct time step (Weinan, 2017). The dynamical system perspective provides mathematically-soume explanation for existing DNN models (Lu et al., 2019). It also leads to new architectures inspired by numerical differential equations and physics (Lu al., 2017; Chen et al.. 2018: Greydanus al., 2019). this vein. one may interpret the training as the parameter identification (PI) of nonlinear dynamics. However, PI typically involves (i) searching dime-independent parameters (ii) given trajectory measurements each time step (Voss al., 2004; Peifer & Timmer, 2007). Neither setup holds in piratical DNNs training, which instead optimizes time- (i.e. layer-) varying parameters given the target measurements only at the final stage.
An alternative perspective, which often leads to a richer analysis, is to recast network weights as control variables. Through this lens, OCP describes w.L.og. the training objective composed of layer- wise loss (e.g. weight decay) and terminal loss (e.g. cross-entropy). This perspective (see Table 1) has been explored recently to provide theoretical statements for convergence and generalization (Weinan et al., 2018: Seidman al., 2020). On the algorithmic side, while OCP has motivated new

---

Published as a conference paper at ICLR 2021
architectures (Benning et al., 2019) and methods for breaking sequential computation (Gunther et al., 2020; Zhang et al., 2019), OCP-inspired optimizers remain relatively limited, often restricted to either specific network class (e.g. discrete weight) (Li & Hao, 2018) small-size dataset (Li et al., 2017).
The aforementioned works are primarily inspired by the Pontryagin Maximum Principle (PMP, Boltyanskii et al. (1960)), which characterizes the first-order optimality conditions OCP. Another parallel methodology which receives little attention is the Approximate Dynamic Programming (ADP, Bertsekas et al. (1995)). Despite both originate from the optimal control theory, ADP differs from PMP in that at each time step a locally optimal feedback policy (as a function of state x;, is computed. These policies, as opposed to the vector update from PMP, are known to enhance the numerical stability of the optimization process when models admit chain structures (e.g. in DNNs) (Liao & Shoemaker, 1992; Tassa et al., 2012). Practical ADP algorithms such as the Differential Dynamic Programming (DDP, Jacobson & Mayne (1970)) appear extensively in modern autonomous systems for complex trajectory optimization (Tassa et al., 2014; Gu, 2017). However, whether they can be lifted to large-scale stochastic optimization, as in the DNN training, remains unclear.
In this work, we make a significant advance to- ward optinal-controo--heereeee training algorithms inspired by ADP. We first show that most exist- ing first- and second-order optimizers can be de- rived from DDP as special cases. Built upon this intriguing connection, we present new class of optimizer which marries the best of both. The proposed method, DDP Neural Optimizer (DDPNOpt), features layer-wise feedback poli- cies, which, as we will show through experiments, improve convergence and robustness. To enable efficient training. DDPNOpt adapts key components including (i) curvature adaption from existing methods, (ii) stabilization techniques used in trajectory optimization, and (iii) an efficient factoriza- tion to OCP. These lift the complexity by orders of magnitude compared with other OCP-inspired baselines, without sacrificing the performance. In summary, we present the following contributions.
Table 1: Terminology mapping
Deep Learning
Optimal Control
J
Total Loss
Trajectory Cost
Activation Vector
State Vector
U
Weight Parameter
Control Vector
f
Layer Propagation
Dynamical System
Φ End-goal Loss
Terminal Cost
E
Weight Decay
Intermediate Cost
We draw a novel perspective of DNN training from the trajectory optimization viewpoint, based on a theoretical connection between existing training methods and the DDP algorithm.
We present a new class of optimizer, DDPNOpt, that performs a distinct backward pass inherited with Bellman optimality and generates layer-wise feedback policies to robustify the training against unstable hyperparameter (e.g. large learning rate) setups.
We show that DDPNOpt achieves competitive performance against existing training methods on classification datasets and outperforms previous OCP-inspired methods in both training performance and runtime complexity. We also identify DDPNOpt can mitigate vanishing gradient.
2 PRELIMINARIES
We will start with the Bellman principle to OCP and leave discussions on PMP in Appendix A. Theorem 1 (Dynamic Programming (DP) (Bellman, 1954)). Define a value function V₁ R IR at each time step that is computed backward in time using the Bellman equation
Ve(x:) (e.
min
(x u.) + (141(fe(Z1, (f)))
Vr(aT) = ((xr),
(1)
where Ix. R" + TT denotes set of mapping from state control space. Then, we have Vo(x0) = J (x0) be the optimal objective value to OCP. Further, let μ1 (a;) ) E T2, be the minimizer of Eq. 1 for each f, then the policy π = {nę (2:)) T- is globally optimal in the closed loop system.
Notation: We will always use as the time step of dynamics and denote subsequence trajectory until time& as R. - hi with क _ ) as the whole. For any real-valued time-dependent function Fe, we denote its derivatives evaluated on a given state-control pair (m; E R" and u, E R'") as Fa,Fi E R", V2 F, F.
E _= Ja E x or simply FL. J'zz and F for brevity. The vector-tensor product, i.e. the contraction mapping the dimension of the vector space, is denoted by Va fee & Σn Va], [f where [Va]: is the i-th element of the vector V2 and [faz] is the Hessian matrix corresponding to that element.
2

---

Published as a conference paper at ICLR 2021
Algorithm 1 Differential Dynamic Programming
Algorithm 2 Back-ppopaaation (BP) with GD
1: Input: á _ [uo))==1 _ (==)T=o
1: Input: _ [u, [u 10 _ {ax ) learning
2: Set V = V and V -
rate
3: for t= = T' 1o do
2: Set pr Jr = VzΦ
4: Compute δuū (6æ+) using v2+1, vat (Eq. 3, 4)
3: for = T 11-110 1 do
5: Compute V2 and Va using Fq.
4: ou; = =-7Vu.d = nlh + fa Pct1)
6: end for
5: p. = Vz = P
7: Set æo
6: end for
8: for to T 1 do
7: for = 0 to T 1 do
9: ui = ui + du; (8æx), where dw: = dt
8: ui
+ du;
10: Øt+1 = ft(ess ui)
9: end for
11: end for
10: ū + [ui JE=
12: + {ut
Hereafter we refer (#t, uz) to the Bellman objective. The Bellman principle recasts minimization over a control sequence to sequence of minimization over each control. The value function V summarizes the optimal cost-to-go at each stage, provided all afterward stages also being minimized,
Differential Dynamic Programming (DDP). Despite providing the sufficient conditions to OCP, solving Eq. I for high-dimensional problems appears to be infeasible, well-known as the Bellman curse of dimensionality. To mitigate the computational burden of the minimization involved each stage, one can approximate the Bellman objective in Eq. with its second-order Taylor expansion. Such an approximation is central to DDP, second-order trajectory optimization method that inherits a similar Bellman optimality structure while being computationally efficient.
Alg. summarizes the DDP algorithm. Given a nominal trajectory (æe, u) with its initial cost J, DDP iteratively optimizes the objective value, where each iteration consists a backward (lines 2-6) and forward pass (lines 7-11). During the backward pass, DDP performs second-order expansion on the Bellman objective Qs each stage and computes the updates through the following minimization,
0 Q
Q
Qt
1
du (6x+)) =
arg min 8u, ( Sice
2 2
6xz d'u
Q
8x
}
(2)
Qua
Quu
Eu:
Oume= Et
f T Vt+1 f Vt+1
Q¹= fh fo T Vi+1
where
Q
et + fu
Vt+1
Q
Qua
8t
Et fu
uu
+ fu T V1+1 fu
Vt+
Jm
+
+ V
x
fu
fu
(3)
We note that all derivatives in Eq. 3 are evaluated at the state-control pair (æt; uy) at time I among the nominal trajectory. The derivatives of Q: follow standard chain rule and the dot notation represents the product of vector with a 3D tensor. In laaa. =2a,=(b, (bb A, A,Z b, E RTT A, E [= denotes the set of all affine mapping from 8x; The analytic solution to Eq. 2 admits a linear form given by
(ox,)) k. + K,8æ, where k
-0 and K. (QQu))-'
(4)
denote the open and feedback gains, respectively. dx; is called the state differential, which will play an important role later in our analysis. Note that this policy is only optimal locally around the nominal trajectory where the second order approximation remains valid. Substituting Eq. 4 back to Eq. gives us the backward update for Ve and Ve
V = Q'
and
Vt. xxx
= ='e - Q (Qu
(5)
In the forward pass, DDP applies the feedback policy sequentially from the initial time step while keeping track of the state differential between the new simulated trajectory and the nominal trajectory.
DIFFERENTIAL DYNAMIC PROGRAMMING NEURAL OPTIMIZER
3.1 TRAINING DNNS AS TRAJECTORY OPTIMIZATION
Recall that DNNs can be interpreted as dynamical systems where each layer is viewed as a distinct time step. Consider egg. the propagation rule in feedforward layers,
x+41 (hi) h ge (2,, u.) W.Y. + b
(6)

---

Published as a conference paper at ICLR 2021
Tt E R and 21+1 E R represent the activation vector at layer t and + 1, with h2 m being the pre-activation vector. o, and 9i respectively denote the nonlinear activation function and the affine transform parametrized by the vectorized weight u, å (vec(W;), b, Eq. 6 can be seen dynamical system (by setting f+ de o It in OCP) propagating the activation vector æt using ut-
Next, notice that the gradient descent (GD) update, denoted dü = a with vy being the learning rate, can be break down into each layer, i.e. dü {ou, T-1 and computed backward by
o arg m + V Vu. "i ou; + fou! ( (1)0
Su.ERm:
where (1z, u.) (us) + Je+1 (Ji u.), u41). Jr(ær) _ ((xT))
(8)
is the per-layer objective' at layer t. It can be readily verified that p: = Vz gives the exact pree-propagation dynamics. Eq. 8 suggests that GD minimizes the quadratic expansion of Jr with the Hessian V2, Jr replaced by J Similarly, adaptive first-order methods, such as RMSprop and Adam, approximate the Hessian with the diagonal of the covariance matrix. Second-order methods, such KFAC and EKFAC (Martens & Grosse, 2015; George al., 2018), compute full matrices using Gauss-News Naustn (GN) approximation:
Vilee BlJu, JU.1
[[ & (x, @ Jn.)) ~ B[(xxx]]] B[(J Jh.).
We now draw a novel connection between the training procedure of DNNs and DDP. Let us first summarize the Back-propagation (BP) with gradient descent in Alg. 2 and compare it with DDP (Alg. 1). At each training iteration, we treat the current weight as the control that simulates the activation sequence a. Starting from this nominal trajectory (æ,, u), both algorithms recursively define some layer-wiss wise objectives (J₃ in Eq. 8 vs V₁ in Eq. 1), compute the weight/control update from the quadratic expansions (Eq. 7 Eq. 2), and then carry certain information (Va,J, J1 vs (V V backward to the preceding layer. The computation graph between the two approaches is summarized in Fig. 1. In the following proposition, make this connection formally and provide conditions when the two algorithms become equivalent.
Back-propagation
DDP Neural Optimizer
at all stages, then the backward dynamics of the value deriva- tive can be described by the Back-pu mack-propagation,
Proposition Assume Que
weight Update Backward Pass
Vi V
vi+1
vi+1
Eq.
Eq.5
Eq.2
V² V Va.J J. Qu -u.J
Duuu 2 J (10)
Ore (-)
but
fi
bug (daz,
-
820
In this case, the DDP policy is equivalent to the
stage-wise Newton, in which the gradient is pre-
vector policy
update value derivatives
conditioned by the bioe inverse Hessian at each layer:
compute weight update
(layer dysuerce)
apply weight update (w. du;)
Figure 1: DDP backward propagates the value derivatives (Va, Vax) instead of V and up- dates weight using layer-wise feedback policy, du, (dæ,), with additional forward propagation.
ke + K.dw, = -)
(1I)
If further we have Quu = IT, then DDP degener- ales to Backk-rropguttonn with gradient descent.
Proof is left in Appendix A.2. Proposition 2 states that the backward pass in DDP collapses to BP when Q Qux vanishes at all stages. In other words, existing training methods can be seen as special cases of DDP when the mixed derivatives (i.e. V Va,u,) of the layer-wise objective are discarded.
3.2 EFFICIENT APPROXIMATION AND FACTORIZATION
Motivated by Proposition 2, we now present a new class of optimizer, DDP Neural Optimizer (DDPNOpt), on training feedforward and convolution networks. DDPNOpt follows the same pro- cedure in vanilla DDP (Alg. 1) yet adapts several key traits arising from DNN training. which we highlight below.
Evaluate derivatives of Q: with layer dynamics. The primary computation in DDPNOpt comes from constructing the derivatives of Q at each layer. When the dynamics is represented by the layer
Hereafter we drop a. in all (-(-) as the layer-wise loss typically involves weight regularization alone.
4

---

Published as a conference paper at ICLR 2021
Table 2: Update rule each layer u, < ut - --,,,,, dc. (Expectation taken over batch data)
Methods
Precondition matrix M.
Update direction de
SGD RMSprop KFAC & EKFAC
E| E[Jur] E Juc
diag( V B Jui & Juc +c) BR] M & E(Q
BlJn, Nel
E Jun
vanilla DDP
BIQ + Que 6xzs]
Ie Qu
DDP
Mi E
diag( V R
@ Qu
+o),
BIQ + Quadass
E. a
V.
propagation (recall Eq. 6 where we set Si = o0 o ge), we can rewrite Eq. 3 as:
2n2 - TV VV Qu = -tt + -u VVV Q = giz TVTTand Vhhia
Qua = gu VLVVV Vingi
(12)
where Vi T x and VhA & T oi absorb the computation of the non-parametrized activation function Note that Eq. 12 expands the dynamics only up to first order, i.e. omitt the tensor products which involves second-orde expansions on dynamics, as the stability obtained by keeping only the linearized dynamics is thoroughly discussed and widely adapted in practical DDP usages (Todorov & Li, 2005). The matrix-vector product with the Jacobian of the affine transform (i.e. Pur I can be evaluated efficiently for both feedforward (FF) and convolution (Conv) layers:
h FF Wia + b. = Fe T V/ W.T.. Lu V/2 = mx 60 Vi
(13)
Cony
+ ge T Vn w/ V% du T = az V/
hg
We Zt.
(14)
where 8, &, and * respectively denote the Kronecker product and (de-)convolution operator.
Curvature approximation. Next, since DNNs are highly over-parametrized models, (i.e. the layer weight) will be in high-dimensional space. This makes Quu and (Quu)= computationally intractable to solve; thus requires approximation. Recall the interpretation draw in Eq. 8 where existing optimizers differ in approximating the Hessian V2, Jr. DDPNOpt adapts the same curvature approximation to Que. For instance, we can approximate Quu simply with an identity matrix It, adaptive diagonal matrix /ElQ @ Q..). or the GN matrix:
Qu Qu [xx @ (a, & VO) = E| &
(15)
Table 2 summarizes the difference in curvature approximation (i.e. the precondition M, for different methods. Note that DDPNOpt constructs these approximations using (V,Q) rather than J since they consider different layer-wise objectives. As a direct implication from Proposition 2, DDPNOpt will degenerate to the optimizer it adapts for curvature approximation whenever all @ vanish.
Outer-product factorization. When the memory efficiency becomes nonnegligible the problem scales, we make GN approximation to V since the low-rank structure at the prediction layer has been observed for problems concerned in this work (Nar et al., 2019; Lezama al., 2018). In the following proposition, we show that for a specific type of OCP, which happens to be the case of DNN training. such low-rank structure preserves throughout the DDP backward pass.
Proposition 3 (Outer- snter-product factorization in DDPNOpt). Consider the OCP where = e, (ue) is independent of xt If the terminal-stage Hessian can be expressed by the outer product of vector z (20(xT) = z (for instance, = V for GN), then we have the factorization for all t:
Que q' E dic Quae d'e s d'e
2 8 2/5
(16)
vex
Pir Lep and 2 are outer-produs vectors which are also computed along the backward pass.
d'
qtt (Qim)) qh q'c
(17)
x
The derivation is left in Appendix A.3. In other words, the outer unter-product factorization at the final layer can be backward propagated to all proceeding layers. Thus, large matrices, such as Q Qi Vt and even feedback policies K,, can be factorized accordingly, greatly reducing the complexity. ax.
5

---

Published as a conference paper at ICLR 2021
Algorithm 3 Differential Dynamic Programming Neural Optimizer (DDPNOpt)
1: Input: dataset D, learning rate 17. training iteration K, batch size B, regularization (aan
2: Initialize the network weights (7()) (i.e. nominal control trajectory)
3: for k == K do
4: Sample batch initial state from dataset, Xo { j D
5: Forward propagate to generate nominal batch trajectory X
Forward simulation
6: Set VT V Va ((xl.))
(2)) and V/T (
V2 2 (anl)) (8)
7:
for =
0 do
Backward Bellman pass
8:
Compute Q Qú Q Oue with Eq. 12 (or Eq. 16-17 if factorization is used)
9:
Compute BlQuul with one of the precondition matrices in Table 2
Store the layer-wise feedback policy du, (oxX,) 1B3 Σ K K, K(00x 8x;
10:
11:
Compute V and V manto with Eq. 5 (or Eq. 16-17 if factorization is used)
12:
V
< V ax(() +Va I if regularization is used
13:
end for
(5)
14:
for = to Dg
Set #0
15:
do
Additional forward pass
u, ut ōu, (6X,), where 8X, -12 Iz Ji=1
16:
a = (( u!))
17:
18:
end for
19:
(k++1) +- {u T-1
20:
end for
Regularization Vaa. Finally, we apply Tikhonov regularization the value Hessian V (line 12 in Alg. 3). This can be seen as placing a quadratic state-cost and has been shown to improve stability on optimizing complex humanoid behavior (Tassa al., 2012). For the application of DNN where the dimension of the state (i.e. vectorized activation) varies during forward/backwaar pass, the Tikhonov regularization prevents the value Hessian from low rank (throught gh TV hh hence we also observe similar stabilization effect in practice.
THE ROLE OF FEEDBACK POLICIES
DDPNOpt differs from existing methods in the use of feedback K, and state differential 5a, The presence of these terms result distinct backward pass inherited with the Bellman optimality. As shown in Table 2, the two frameworks differ in computing the update directions d,, where the Bellman formulation applies the feedback policy through additional forward pass with òz, We have built the connection between these two d, in Proposition 2. In this section, we further characterize the role of the feedback policy K; and state differential 8x, during optimization.
First we discuss the relation of DDPNOpt with other second-order methods and highlight the role feedback during training. To so let us consider the example Fig. 2a. Given an objective expanded at (Mg, uo), standard second-order methods compute the Hessian w.r.t u then apply the update du = - - Lu (shown as green arrows). DDPNOpt differs in that it also computes the mixed partial derivatives, i.e. Lux. The resulting update law has the same intercept but with an additional feedback term linear in 6x (shown as red arrows). Thus, DDPNOpt searches for an update from the affine mapping 1/mm. (Eq. 2), rather than the vector space mm (Eq. 7).
Next, to show how the state differential dz, arises during optimization, notice from Alg. I that á can be compactly expressed 2, = F1 difference when new updates duz (ōæ) are applied until layer I - 1. Now, consider the 2D example in Fig 2b. Back-propagation proposes the update directions (shown as blue arrows) from the first-order derivatives expanded along the nominal trajectory (æ, ū) However, as the weight at each layer is correlated, parameter updates from previous layers dū; affect proceeding states (æ; it s). thus the trustworthiness of their descending directions. As shown in Fig 2c, cascading these (green) updates may cause an over-shor shors w.r.t. the designed target. From the trajectory optimization perspective, much stabler direction will be instead V Jr(Wr, u.) (shown as orange), where the derivative is
Sü" (d Therefore, 8x, t. x; captures the state
F, & o..... o denotes the compasitional dynamics propagating ao with the control sequence (u, 14-

---

Published as a conference paper at ICLR 2021
(a)
(b) Back-propngation with GD
(c) Weight Update
*
Targer
Target
Lead Les
22
1Ag
bx
(4t.4)
(6a)
Lea
Leg
E
Legend:
(ar Me) (S10)
Wisii Me) (80
Va me)
Kg
Figure 2: (a) toy illustration of the standard update (green) and the DDP feedback (red). The DDP policy in this case is a line lying at the valley of objective L. (be) Trajectory optimization viewpoint of DNN training. Green and orange arrows represent the proposed updates from GD and DDP.
evaluated the new cascading state it, which accounts for previous updates, rather than the original state xt. This is exactly what DDPNOpt proposes, as we can derive the relation (see Appendix A.5),
Kg arg min V[V J (át; un dur ( - V (2 ue)l (8m,)
(18)
Thus, the feedback direction compensates the over-shoot by steering the GD update toward Jr u,) after observing ōæ,, The difference between J u.) be neglected especially during early training when the loss landscape contains nontrivial curvature everywhere (Alain et al., 2019). In short, the use of feedback K, and state differential oz, arises from the fact that deep nets exhibit chain structures. DDPNOpt feedback policies thus have stabilization effect on robustifying the training dynamics against e.g. .m.mpprr hyper-paramesd unstable training. This perspective (i.e. optimizing chained parameters) is explored rigorously in trajectory optimization, where DDP is shown to be numerically stabler than direct optimization such as Newton method (Liao & Shoemaker, 1992).
and V,, uz) cannot
which may cause
Remarks on other optimizers. Our discussions so far rigorously explore the connection between DDP and stage/layer-wise Newton, thus include many popular second-order training methods. Gen- eral Newton method coincides with DDP only for linear dynamics (Murray & Yakowitz, 1984), despite both share the same convergence rate when the dynamics is fully expanded to second order. We note that computing layer-wise value Hessians with only first-order expansion on the dynamics (Eq. 12) resembles the computation in Gauss-Newton method (Botev et al., 2017). For other control- theoretic methods, e.g. PID optimizers (An et al., 2018), they mostly consider the dynamics over training iterations. DDPNOpt instead focuses on the dynamics inherited in the DNN architecture.
EXPERIMENTS
5.1 PERFORMANCE ON CLASSIFICATION DATASET
Networks & Baselines Setup. We first validate the performance of training fully-connected (FCN) and convolution networks (CNN) using DDPNOpt on classification datasets. FCN consists of fully-comnected layers with the hidden dimension ranging from 10 to 32, depending the size of the dataset. CNN consists of 4 convolution layers (with 3x3 kernel, 32 channels), followed by fully-connected layers. We use ReLU activation all datasets except Tanh for WINE and DIGITS to better distinguish the differences between optimizers. The batch size is set to 8-32 for datasets trained with FCN, and 128 for datasets trained with CNN. As DDPNOpt combines strengths from both standard training methods and OCP framework, we select baselines from both sides. This includes first-order methods, i.e. SGD (with tuned momentum), RMSprop, Adam, and second-order method EKFAC (George et al., 2018), which is recent extension of the popular KFAC (Martens & Grosse, 2015). For OCP-inspired methods, we compare DDPNOpt with vanilla DDP and E-MSA (Li et al., 2017), which is also second-order method yet built upon the PMP framework. Regarding the curvature approximation used in DDPNOpt (M, in Table 2), we found that using adaptive diagonal and GN matrices respectively for FCNs and CNNs give the best performance in practice. We leave the complete experiment setup and additional results in Appendix A.6.
Training Results. Table 3 presents the results over 10 random trials. It clear that DDPNOpt outperforms two OCP baselines on all datasets and network types. In practice, both baselines suffer from unstable training and require careful tuning the hyper- syper-parameters. In fact, are not able to obtain results for vanilla DDP with any reasonable amount of computational resources when the problem size goes beyond FC networks. This is in contrast to DDPNOpt which adapts amortized
7

---

Published as a conference paper at ICLR 2021
Table 3: Performance comparison on accuracy (%). All values averaged over 10 seeds.
Standard baselines RMSProp
DCP-inspired baselines
DataSet
DDPNOpt (ours)
SGD-m m
Adam
EKFAC
E-MSA
vanilla DDP
CNN Feed-forward
WINE
94.35
98.10
98.13
94.60
93.56
98.00
98.18
DIGITS
95.36
94.33
94.98
95.24
94.87
91.68
95.13
MNIST
92.65
91.89
92.54
92.73
90.24
90.42
93.30
F-MNIST
82.49
83.87
84.36
84.12
82.04
81.98
84.98
MNIST
97.94
98.05
98.04
98.02
96.48
98.09
SVHN
89.00
88.41
87.76
90.63
79.45
N/A
90.70
CIFAR-10 10
71.26
70.52
70.04
71.85
61.42
71.92
Table 4: Computational complexity in backward pass. (B: batch size, X: hidden state dim., L: # of layers)
wall-clock time
10a
2.00
Adam EXPAC
vardie DDP
Method
Adam
Vanilla DDP
DDPNOpt
20
10a
Memory Speed
O(X²L) O(BX²L)
O(BXLL)
O(X BX) O(BX²L)
O(B'xL)
Batch Size
Figure 3: Runtime comparison on MNIST.
curvature estimation from widely-used methods; thus exhibits much stabler training dynamics with superior convergence. In Table 4, we provide the analytic runtime and memory complexity among different methods. While vanilla DDP grows cubic w.r.t. BX, DDPNOpt reduces the computation by orders of magnitude with efficient approximation presented in Sec. 3. As a result, when measuring the actual computational performance with GPU parallelism, DDPNOpt runs nearly fast standard methods and outperforms E-MSA by a large margin. The additional memory complexity, when comparing DDP-inspired methods with Eack-propagation methods, comes from the layer-wise feedback policies. However, DDPNOpt is much memory-efficient compared with vanilla DDP by exploiting the factorization in Proposition 3.
Ablation Analysis. On the other hand, the performance gain between DDPNOpt and standard methods appear comparatively small. We conjecture this is due the inevitable of similar curvature adaptation, as the local geometry of the landscape directly affects the convergence behavior. To identify scenarios where DDPNOpt best shows its effectiveness, we conduct an ablation analysis on the feedback mechanism. This is done by recalling Proposition 2: when Que vanishes. DDPNOpt degenerates to the method associated with each precondition matrix. For instance, DDPNOpt with identity (resp. adaptive diagonal and GN) precondition M, will generate the same updates as SGD (resp. R.MSprop and EKFAC) when all Qua are zeroed out. other words, these DDPNOpt variants can be viewed as the -eeeextension to existing baselines.
In Fig. 4a we report the performance difference between each baseline and its associated DDPNOpt variant. Each grid corresponds to distinct training configuration that is averaged over 10 random trails, and we keep all sopee-parameters (e.g. learning rate and weight decay) the same between baselines and their DDPNOpt variants. Thus, the performance gap only comes from the feedback policies, or equivalently the update directions in Table 2. Blue (resp. red) indicates an improvement (resp. degradation) when the feedback policies presented. Clearly, the improvement over baselines remains consistent across most hyper-parameter setups, and the performance gap tends to become obvious as the learning rate increases. This aligns with the previous study on numerical stability (Liao & Shoemaker, 1992). which suggests the feedback can stabilize the optimization when e.g. larger control updates are taken. Since larger control corresponds to a further step size in the application of DNN training, one should expect DDPNOpt to show its robustness as the learning rate increases. As shown in Fig. 4b, such a stabilization can also lead smaller variance and faster convergence. This sheds light the benefit gained by bridging two seemly disconnected methodologies between DNN training and trajectory optimization.
5.2 DISCUSSION ON FEEDBACK POLICIES
Visualization of Feedback Policies. To understand the effect of feedback policies more perceptually, in Fig. 5 we visualize the feedback policy when training CNNs. This is done by first conducting
8

---

Published as a conference paper at ICLR 2021
(a) DDPNOpt vs SGD (training loss)
DDPMOpt vs RMSprop ttraining loss)
DDPNOpt vs BKFAC Itraining loss)
(b)
Config:1f 0 Vixele
0.25
0.03
0.07
Trah LoGs
DoPtop:
0.09
0.0
0.30
57
0.1
0.1
Agguro
-04
-0.07
Leaming Ratte
fe-5
300
Iasattom
2000
1990
DDRNOst facouracy
DDPNOpt RMSprop (accuracy %)
DOPNOpt (accuracy
Configg 0.01, Vooele
10
0.05
Train Loss
RMBorop
DOPNCp:
2.-
0.02
0.09
68
-10
0.045
25 1404 St
1603
09 1s 05 56 1o
16 07 52 Se 16
300
2008
1.90
Reaaioon
Figure 4: (a) Performance difference between DDPNOpt and baselines on DIGITS across hyper- parameter grid. Blue (resp. red) indicates improvement (resp. degradation) over baselines. We observe similar behaviors on other datasets. (b) Examples of the actual training dynamics.
6zuax
62
(a)
(b)
6
SGD-VER
Updaate Norm
0.2
EXFAC
7
SGD
0.1
DOPMOp122d
DDPNOpt
DDPkOpe2nd
8
1000
2000
3000
4.000
Itertions
Layer
Figure 6: Training 9-layer sigmoid-activated FCN on DIGITS using MMC loss. DDPNOpt2nd denotes when the layer dynamics is fully expanded the second order.
Figure 5: Visualization of the feedback policies MNIST.
singular-valuu value decomposition the feedback matrices K,, then projecting the leading right-singular vector back to image space (see Alg. 4 and Fig. 7 in Appendix for the pseudo-code). These feature maps, denoted dæ in Fig. 5, correspond the dominating differential image that the policy shall respond with during weight update. Fig. 5 shows that the feedback policies indeed capture non-trivial visual features related the pixel-wise difference between spatially similar classes, e.g. (8.3) 3) or (7, 1). These differential maps differ from adversarial perturbation (Goodfellow et al., 2014) as the former directly links the parameter update the change activation; thus being more interpretable.
Vanishing Gradient. Lastly, we present an interesting finding on how the feedback policies help mitigate vanishing gradient (VG), notorious effect when DNNs become impossible to train as gradients vanish along Back- procaprrppgation. Fig. 6a reports results training sigmoid-activated DNN on DIGITS, We select SGD- VGR, which imposes a specific regularization to mitigate VG (Pascanu al., 2013), and EKFAC as our baselines. While both baselines suffer to make any progress, DDPNOpt continues to generate non-trivial updates as the state state-dependent feedback, i.e. K remains active. The effect becomes significant when dynamics is fully expanded to the second order. As shown in Fig. 6b, the update norm from DDPNOpt is typically 5-10 times larger. We note that in this experiment, replace the cross-entropy (CE) with Max-lahalanobis center (MMC) loss, new classification objective that improves robustness on standard vision datasets (Pang et al., 2019). MMC casts classification distributional regression, providing denser Hessian and making problems similar to original trajectory optimization. None of the algorithms escape from VG using CE. We highlight that while VG is typically mitigated on the architecture basis, by having either unbounded activation function or residual blocks, DDPNOpt provides an alternative from the algorithmic perspective.
6 CONCLUSION
In this work, we introduce DDPNOpt, new class of optimizer arising from novel perspective by bridging DNN training to optimal control and trajectory optimization. DDPNOpt features layer-wise feedback policies which improve convergence and robustness to syper-parameters over existing optimizers. It outperforms other OCP-inspired methods both training performance and scalability. This work provides algorithmic insight and bridges between deep learning and optimal control.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
The authors would like to thank Chen- Chen-Hsuan Lin, Yunpeng Pan, Yen-Cheng Liu, and Chia- Wen Kuo for many helpful discussions the paper. This research supported by NSF Award Number 1932288.
REFERENCES
Guillaume Alain, Nicolas Le Roux, and Pierre-Antoine Manzagol. Negative eigenvalues of the hessian in deep neural networks. arXiv preprint N.XI::1902.02660 2019.
Wangpeng An, Haoqian Wang. Qingyun Sun, Jun Xu, Qionghai Dai, and Lei Zhang. A pid controller approach for stochastic optimization of deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8522- 1221, 2018.
the
Richard Bellman. The theory of dynamic programming. Technical report, Rand corp santa monica ca, 1954.
Martin Benning, Elena Celledoni, Matthias Ehrhardt, Brynjulf Owren, and
Schönlieb. Deep learning as optimal control problems: models and numerical methods. arXiv preprint arXiv: 05650, 2019.
Dimitri P Bertsekas, Dimitri Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control. Athena scientific Belmont, MA, 1995.
Vladimir Grigor's evich Boltyanskii, Revaz Valer' yanovich Gamkrelidze, and Lev Semenovich Pon- tryagin. The theory of optimal processes. i. the maximum principle. Technical report, TRW SPACE TECHNOLOGY LABS LOS ANGELES CALIF, 1960.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. In Proceedings of the 34th International Conference Machine Learning- Cearning-Volume 70, pp. 557-565. JMLR. org, 2017.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary dif- ferential equations. In Advances in Neural Information Processing Systems, pp. 6572-6583 2018.
Gamkrelidze. Principles of optimal control theory, volume 7. Springer Science & Business Media, 2013.
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in a kronecker factored eigenbasis. Advances in Neural Information Processing Systems, pp. 9550-9560) 2018.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint
2014.
Samuel Greydamus, Misko Dzamba, and Jason Yosinski. Hamiltonian neural networks. In Advances in Neural Information Processing Systems, pp. 15353-15363, 2019.
Tianyu Gu. Improved trajectory planning for on-road self-driving vehicles via combined graph search, optimization & topology analysis. PhD thesis, Carnegie Mellon University, 2017.
Stefanie Gunther, Lars Ruthotto, Jacob B Schroder, Eric C Cyr, and Nicolas R Gauger. parallll training of deep residual neural networks. SIAM Journal on Mathematics of Data Science, 2(1): 1-23, 2020.
D.H. Jacobson and D.Q. Mayne. Differential Dynamic Programming. Modern analytic and computa- tional methods in science and mathematics. American Elsevier Publishing Company, 1970. URL https: ttttss:/bbooks /books................o.oo...k.. google. cott/
OAAAAAAAAAAAAAAAA
José Lezama, Qiang Qiu, Pablo Musé, and Guillermo Sapiro. Ole: Orthogonal low-rank embedding- a plug and play geometric loss for deep learning. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 8109-81 18, 2018.
10

---

Published as a conference paper at ICLR 2021
Qianxiao Li and Shuji Hao. An optimal control approach to deep learning and applications to snurrete-weight neural networks. arXiv preprint arXiv:1803.0122 2018.
Qianxiao Li, Long Chen, Cheng Tai, and E Weinan. Maximum principle based algorithms for deep learning. The Journal of Machine Learning Research, 18(1):5998 (()):5598-6026, 2017.
Li-zhi Liao and Christine A Shoemaker. Advantages of differential dynamic programming over newton's method for discrete-time optimal control problems. Technical report, Cornell University, 1992.
Guan-Homp Liu and Evangelos A Theodorou. Deep learning theory review: An optimal control and dynamical systems perspective. arXiv preprint arXiv:1908. 2019.
Yiping Lu, Aoxiao Zhong, Quanzheng Li, and Bin Dong. Beyond finite layer neural networks: Bridging deep architectures and numerical differential equations. arXiv preprint arXiv:1710.10121 2017.
Yiping Lu, Zhuohan Li, Di He, Zhiqing Sun, Bin Dong, Tao Qin, Liwei Wang, and Tin-Yan Liu. Understanding and improving transformer from multi-particle dynamic system point of view. arXiv preprint arxiv:1906 02762,, 2019.
James Martens and Roger Grosse. Optimizing neural networks with kronecker-ffactrred approximate curvature. In International conference on machine learning, pp. 2408-248222 2417, 2015.
DM Murray and SJ Yakowitz. Differential dynamic programming and newton's 's method for discrete optimal control problems. Journal of Optimization Theory and Applications, 43(3):395 1984.
Kamil Nar, Orhan Ocal, S Shankar Sastry, and Kannan Ramchandran. Cross-entropy loss and low-rank features have responsibility for adversarial examples. arXiv preprint 181.00000 2019.
Tianyu Pang, Kun Xu, Yinpeng Dong, Chao Du, Ning Chen, and Jun Zhu. Rethinking softmax cross-entropy loss for adversarial robustness. arXiv preprint arXiv: 0e..//955002000 2019.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318, 2013.
M Peifer and Timmer. Parameter estimation in ordinary differential equations for biochemical processes using the method of multiple shooting. IET Systems Biology, 1(2):78-88) 88, 2007.
Lev Semenovich Pontryagin, EF Mishchenko, VG Boltyanskii, and RV Gamkrelidze. The mathemat- ical theory of optimal processes. 1962.
Jacob Seidman, Mahyar Fazlyab, Victor M Preciado, and George Pappas. Robust deep learning as optimal control: Insights and convergence guarantees. Proceedings of Machine Learning Research vol xxx, 1:14, 2020.
Yuval Tassa, Tom Erez, and Emanuel Todorov. Synthesis and stabilization of complex behaviors through online trajectory optimization. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 19906-4113 IEEE, 2012.
Yuval Tassa, Nicolas Mansard, and Emo Todorov, Control-limited differential dynamic programming In 2014 IEEE International Conference Robotics and Automation (ICRA), pp. 1168-1175. IEEE, 2014.
Emanuel Todorov and Weiwei Li. A generalized iterative lgg method for locally-optimal feedback control of constrained nonlinear stochastic systems. In Proceedings of the 2005, American Control Conference, 2005., pp. 300-306. IEEE, 2005.
Henning Voss, Jens Timmer, and Jürgen Kurths. Nonlinear dynamical system identification from uncertain and indirect measurements. International Journal of Bifurcation and Chaos, 14(06): 1903-1933, 2004.
Weinan. A proposal on machine learning via dynamical systems. Communications in Mathematics and Statistics, 5(1):1-11, 2017.
11

---

Published as a conference paper at ICLR 2021
E Weinan, Jiequn Han, and Qianxiao Li. A mean-field optimal control formulation of deep learning. arXiv preprint arXiv:1807.01033 2018.
Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European conference on computer vision, pp. 818-898 833. Springer, 2014.
Dinghuai Zhang, Tianyuan Zhang, Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate once: Accelerating adversarial training via maximal principle. arXiv preprint 1 00877. 2019.
A APPENDIX
A.1 CONNECTION BETWEEN PONTRYAGIN MAXIMUM PRINCIPLE AND DNNS TRAINING
Development of the optimality conditions to OCP can be dated back to 1960s, characterized by both the Pontryagin's Maximum Principle (PMP) and the Dynamic Programming (DP). Here we review Theorem of PMP and its connection to training DNNs.
Theorem 4 (Discrete-time PMP (Pontryagin et al., 1962)), Let ū² be the optimal control trajectory for OCP and x" be the corresponding state trajectory. Then, there exists a co-state trajectory p A (pi)T=) such that
Ei+1 Vp He Pi+1: ui) 46 20
(19a)
P: = Va Pi+1: ui) Pr = V (x)))
(19b)
u = arg min He (z) 1)
(19c)
vER"
where H₁ IR" IR"
R m
I the discrele-time Hamiltonian given by
He (zt, p+t1, 2 (x us) + f ut),
(20)
and Eq. 19b is called the adjoint equation.
The discrete-time time PMP theorem can be derived using KKT conditions, in which the co-state pt is equivalent to the Lagrange multiplier. Note that the solution to Eq. 19c admits an open-loop process the sense that it does not depend on state variables. This contrast to the Dynamic Programming principle, in which a feedback policy is considered.
is natural to ask whether the necessary condition in the PMP theorem relates to first-order optimiza- tion methods in DNN training. This is indeed the case as pointed out in Li et al. (2017):
Lemma 5 (Li et al. (2017)). Back-propagation satisfies Eq. 19b and gradient descent iteratively solves Eq. 19c.
Lemma 5 follows by first expanding the derivative of Hamiltonian w.r.t. Tt.
V Hy (Z,, P,+1, u.) = V., (e u+) + V Se(re, ue) Ppt1 = Vn, J(ū; ap)
(21)
Thus, Eq. 19b is simply the chain rule used the Back propappopa.tionn When H, is differentiable w.r.t. Uz one can attempt to solve Eq. 19c by iteratively taking the gradient descent. This will lead to
(k+1)
(k) u
1/ u: Ha Put1, u)) u, (k)
1/ u, J (ū;
(22)
where & and 77 denote the update iteration and step size. Thus, existing optimization methods can be interpreted as iterative processes to match the PMP optimality conditions.
Inspired from Lemma 5, Li et al. (2017) proposed PMP-inspired method, named Extended Method of Successive Approximations (E-MSA), which solves the following augmented Hamiltonian
H2 (Ix, 1 Ur L P.) He (we, Pe+1, un)
(23)
+ 2 [441 - fe wi)l + 20 lpp - Va, Hell
12

---

Published as a conference paper at ICLR 2021
H2 is the original Hamiltonian augmented with the feasibility constraints on both forward states and backward co-states. E-MSA solves the minimization
i arg min He (Ite Po+1; We 1:+1,
(24)
14,
with L-BFGS per layer and per training iteration. As a result, we consider E-MSA also as second-order method.
A.2 PROOF OF PROPOSITION 2
Proof. We first prove the following lemma which connects the backward pass between two frame- works in the degenerate case.
Lemma 6, Assume Qua at all stages, then we have
V J. and
V
V m
J
Vt.
(25)
mr
Proof. is obvious to that Eq. 25 holds at t = T. Now, assume the relation holds at t - and observe that at the time t, the backward passes take the form
= S V Vanl Va Vt 2ee QTT - -Quu Va, Cle fe Ve'nn
V Q2e (Quu)
J3 = V2
where we recall J, l + J (Je) in Eq. 8.
Now, Eq. 11 follows by substituting Eq. 25 to the definition of Ou and Quu
Qu tu + fu V++1 Ey fu Venn J V Vun!! Q'u,. gt fu Vt+1 fū
Vt-1 .un
pr + fú (V J)L +
Vanni Sun
-ua, (e + TV. #. J} V
Consequently, the DDP feedback policy degenerates to layer- laser-wise Newton update.
A.3 PROOF OF PROPOSITION 3
Proof. We will prove Proposition 3 by backward induction. Suppose at layer + 1, we have Vt+1 ++1
& zt+1 and &, = Ee(u)). then Eq. becomes a
um
Que = ftt T Vi+1
wa f f (z
(+1
+ (fe _+11
2 @ (ft 2 ,+1) +1 (ful x
Qua fu
T V1+1 gl fu T
(z+t1
11 x (fu T z (+1).
Setting dh = Se 2 1+1 and s: = su 2 will give the first part of Proposition 3.
Next, to show the same factorization structure preserves through the preceding layer, it is sufficient to show Vtc 2/ & zt for some vector 2 This indeed the case.
Vt = Qina Q (Q ua
q' q' (q', @ T (- @ ogh)
q'm & q' (q (Q ) (i, @ gi))
where the last equality follows by observing qu. (Quu)) is scalar.
Set 2 v1 T (QQu.) -'g;, q% will give the desired factorization.
13

---

Published as a conference paper at ICLR 2021
A.4 DERIVATION OF EQ. 12
For notational simplicity, we drop the superscript and denote V22 of the value function at the next state.
Vn Vei (28++1 1) as the derivative
Qu lu Vu lu o
T [vr3 Quu = luu + du (a
= Luu + In Iu (Voo1 + Iul G
ToT δ
(ont) + (oul) oo
du
du
-uu gu V Jh + g (VTToonn onngu) Jun %
Lun + Iu (Vnn + Va ou + Vn Jun
The last equation follows by recalling Vn a Vo and Vhn - o Vo V Follow similar derivation, we have
Qx le + 92 Vn
Qux = lex + 9 (Vi + V" ona)ge + Vn Iæx
(26)
Qux = Lux + I (Vhh + Va Jnhlge + Vn Juæ
Remarks. For feedforward networks, the computational overhead in Eq. 12 and 26 can be mitigated by leveraging its affine structure. Since g is bilinear æ; and u, the terms Itw and Ium vanish. The tensor Pum admits a sparse structure, whose computation can be simplified to
( =1 iff (k: 1)m++1 +i,
(27)
V -Gun ((
V%
For the coordinate-wise nonlinear transform, of1 and of are diagonal matrix and tensor. In most learning instances, stage-wise losses typically involved with weight decay alone; thus the terms et fet fu also vanish.
A.5 DERIVATION OF EQ. 18
Eq. 18 follows by an observation that the feedback policy K,ōx, (Quu)) -1 8x, stands as the minimizer of the following objective
arg min Kidx;= (8,
| Q(x; + 8z;, un + (ūx() - Vu, Q( ut)l
(28)
where ('(x)) denotes all affine mappings from óz, to or, and ||:|| can be any proper norm in the Euclidean space. Eq. 28 follows by the Taylor expansion of Q(+; + dez, u, + du,) its first order,
Va, Q(x; 8x,, u, + 8w:) Vu, Q(1,, u,) Q 8x; + Qun
When Q J, we will arrive at Eq. 18. From Proposition 2, know the equality holds when all Q vanish for s > t. other words, the approximation in Eq. 18 becomes equality when all aferward layer-wise wiver-wiseeao objectives > are expanded only w.r.t. U
A.6 EXPERIMENT DETAIL
A.6.1 SETUP
Clarification Dataset. All networks in the classification experiments are composed of 5-6 layers. For the inter- all dataset,
Table 5:
search
mediate layers, use ReLU activation except Tanh on WINE and DIGITS. We use identity mapping the last prediction layer on all dataset except WINE, where we use sigmoid instead to help distinguish the performance among optimizers. For feedforward net- works, the dimension of the hidden state is set to 10-32. On the other hand, we standard x convolution kernels for all CNNs. The batch size is set 8-32 for dataset trained with feedforward networks,
Methods
Learning Rate
SGD Adam & RMSprop EKFAC
(7e-2, 5e-1)
(7e-4, 1e-2)
(1e-2, 3e-1)
14

---

Published as a conference paper at ICLR 2021
and 128 for dataset trained with convolution networks. For each baseline we select its own hyper- parameter from an appropriate search space, which we detail in Table 5. We use the implementation in for EKFAC and implement our E-MSA in Py PyTorch since the official code released from Li et al. (2017) does not support GPU implementation. We impose the GN factorization presented in Proposition 3 for all CNN training. Regarding the machine information, we conduct our experiments on GTX 1080 TI, RTX TITAN, and four Tesla V100 SXM2 16GB.
https: // gi thub. com Thrandis EKEAC-pytore
Procedure to Generate Fig. 5. First, we perform standard DDPNOpt steps to compute layer-wise policies. Next, we conduct singular-valus decomposition on the feedback matrix (k2, K2). In this way, the leading right-singular vector corresponding to the dominating that the feedback policy shall respond with. Since this vector with the same dimension as the hidden state, which is most likely not the same the image space, we project the vector back to image space using the techniques proposed in (Zeiler& & Fergus, 2014). The pseudo code and computation diagram are included in Alg. 4 and Fig. 7.
22
82t mar
Algorithm 4 Visualizing the Feedback Policies
1: Input: Image æ (we drop the time subscript for nota- tional simplicity, iee = zo)
Convax3
DeConw3x3
Perform backward pass of DDPNOpt.
Compute
Comv3x3
k.
K
Mauxx (K,)
(ke, Kt) backward
3: Perform SVD on K;
DDPNOpt backward
4: Extract the right-singular vector corresponding the largest singular value, denoted Umax E Rd
Comvax3
value func. Min.
weight computate
5: Project Fmax back to image space using decon- volution procedures introduced in (Zeiler & Fergus, 2014)
k;
K
SVD
Hidden Sate Projection
J 5:
(Zeiler Fergus (201 4))
Figure 7: Pictorial illustration for Alg. 4.
A.6.2 ADDITIONAL EXPERIMENT AND DISCUSSION
Batch trajectory optimization on synthetic dataset. One of the difference between DNN training and trajectory optimization is that for the former, we aim to find an ultimate control law that can drive every data point the training set, or sampled batch, to its designed target. Despite seemly trivial from the ML perspective, this is a distinct formulation to OCP since the optimal policy typically varies at different initial state. As such, we validate performance of DDPNOpt in batch trajectories optimization on synthetic dataset, where sample data from & E (5, 8, 12, 15) Gaussian clusters in R Since conceptually a DNN classifier can be thought of as a dynamical system guiding trajectories of samples toward the target regions belong to their classes, DDPNOpt to show its effectiveness on batch training, the feedback policy must act as an ensemble policy that combines the locally optimal policy of each class. Fig. 8 shows the spectrum distribution, sorted in a descending order, of the feedback policy in the prediction layer. The result shows that the number of nontrivial eigenvalues matches exactly the number of classes in each setup (indicated by the vertical dashed line). As the distribution in the prediction layer concentrates to l bulks through training. the eigenvalues also increase, providing stronger feedback to the weight update.
hypothesize that for the
Clusters
Clusters
12 Clusters
15 Clusters
Egenvalles
50
50
1.5
100
100
100
1.0
100
150
150
250
250
1.0
250
250
0.5
0.5
0.0
0.0
10
10
20
10
20
10
20
Order of Largest Eigenvalues
Figure 8: Spectrum distribution on synthetic dataset.
Ablation analysis on Adam. Fig. 9 reports the ablation analysis on Adam using the same setup as in Fig. 4a, iee. keep all hyper-parameters the same for each experiment that the performance
15

---

Published as a conference paper at ICLR 2021
difference only comes from the existence of feedback policies. It is clear that the improvements from the feedback policies remain consistent for Adam optimizer.
DOPNOpt vs Adam frriiingg loss]
DOPNOpt vs Adamn (accuracy)
0,015
0.015
0.04
Learning Rete
0,025
0.025
0.0
0,00
2.63
0.23
0.945
-0.1..045
-0.04
16:9
16
16:06
09
1e
16:07
16:66
Vix regulariization
Figure 9: Additional experiment for Fig. 4a where compare the performance difference between DDPNOpt and Adam. Again, all grids report values averaged over 10 random seeds.
Ablation analysis DIGITS compared with best-tuned baselines. Fig. 4 reports the performance difference between baselines and DDPNOpt under different hyperparameter setupts. Here, we report the numerical values when each baseline uses its best-tuned learning rate (which the values report in Table 3) and compare with its DDPNOpt counterpart using the same learning rate. As shown in Tables 6, 7, and 8, for most cases extending the baseline to accept the Bellman framework improves the performance.
Table 6: Learning rate 0.1
SGD
DDPNOpt with M. 1
Train Loss
0.035
0.032
Accuracy (%)
95.36
95.52
Table 7: Learning rate = 0.001
RMSprop
DDPNOpt with M: diag( (iag(v/B(Q /B[Qu Q.] +c)
Train Loss
0.058
0.052
Accuracy (%)
94.33
94.63
Table 8: Learning rate = 0.03
EKFAC
DDPNOpt with M, B[x,2|] B[VV
Train Loss
0.074
0.067
Accuracy (%)
95.24
95.19
Numerical absolute values in ablation analysis (DIGITS). Fig. 4a reports the relative performance between each baseline and its DDPNOpt counterpart under different learning rate and regularization setups. In Table and 10, report the absolute numerical values of this experiment. For instance, the most left-upper grid in Fig. 4a, tee the training loss difference between DDPNOpt and SGD with learning rate 0.4 and Vas regularization 5 10-5, corresponds to 0.1974 0.1662 in Table 9. All values in these tables are averaged over 10 seeds.
Table 9: Training Loss. (EV,a, denotes the Tikhonov regularization on V
DDPNOpt with M, I,
SGD
EVsu = 10-5
1 x 10
5 x 10
x 10
Learn Rate
0.4
0.1974
0.1662
0.1444
0.1322
0.1067
0.6
0.5809
0.4989
0.4867
0.3263
0.2764
0.7
1.0493
0.9034
0.8240
0.6592
0,5381
0.8
1.7801
1.6898
1.4597
1.1784
1.3166
16

---

Published as a conference paper at ICLR 2021
DDPNOpt with M, = diag(
/ @ Qu. +
RMSprop
CVin
x 10-
1 x 10
x 10
1 1x 10
Learn Rate
0.01
0.19-19
0.1638
0.1714
0.1746
0.1588
0.02
0.4691
0.4559
0.4489
0.4390
0.4773
0.03
0.8156
0.7675
0.7736
0.7790
0.7893
0.045
1.3103
1.2740
1.2956
1.2568
1.2758
DDPNOpt with M. = E[a..]]]
@ V
[
EKFAC
1 x 10-
5 x 10"
5 x 10
x 10
Learn Rate
0.05
0.0757
0.0636
0.0659
0.0691
0.0717
0.09
0.2274
0.2087
0.2164
0.2091
0.2223
0.3260
0.2771
0.3003
0.2543
0.2510
0.3
0.5959
0.5462
0.5282
0.5299
0.5858
Table 10: Accuracy (%) (eVer denotes the Vas regularization.)
DDPNOpt with M,
SGD
<Van 5 10-5
10
5 x 10
10-3
Learn Rate
0.4
91.46
91.98
92.71
92.90
93.12
0.6
81.73
83.64
84.09
88.39
89.39
0.7
70.48
73.42
75.44
80.62
82.87
0.8
55.76
57.70
62.82
70.23
65.01
DDPNOpt with M. diag(
B[Q
Qu]
+
+c)
RMSprop
EVem
x 10-
5 10-6
x
Leam Rate
0.01
91.48
92.14
91.80
91.73
92.52
0.02
84.15
84.82
85.02
85.23
83.00
0.03
73.07
75.24
75.73
74.29
74.16
0.045
59.80
59.16
60.98
61.75
59.87
DDPNOpt with M. B[x
B(VAV
EKFAC
VVen
10
5
5 10
10
Learn Rate
0.05
93.70
93.84
93.88
94.31
94.06
0.09
90.84
91.13
91.45
91.23
91.24
0.1
88.88
89.69
89.89
90.18
90.94
0.3
81.82
83.79
84.09
84.15
82.55
More experiments on vanishing gradient. Recall that Fig. reports the training performance using MMC loss on Sigmoid-activated networks. In Fig. 10a, we report the result when training the same networks but using CE loss (notice the numerical differences in the y axis for different objectives). None of the presented optimizers were able to escape from vanishing gradient, as evidenced by the vanishing update magnitude. On the other hands, changing the networks to ReLU-activated networks eliminates the vanishing gradient, as shown in Fig. 10b.
Fig. reports the performance with other first-order adaptive optimizers including Adam and RMSprop. In general, adaptive first-order optimizers more likely to escape from vanishing gradient since the diagonal precondition matrix (recall M, E[Ju, @ Ju..] in Table 2) rescales the vanishing update to fixed norm. However, shown in Fig. 11, DDPNOpt (the variant of DDPNOpt that utilizes similar adaptive first-order precondition matrix) converges faster compared with these adaptive baselines.
Fig. 12 illustrates the selecting process on the learing-rate tuning when we report Fig. The training performance for both VGD and EKFAC remains unchanged when tuning the learning rate. In
17

---

Published as a conference paper at ICLR 2021
practice, observe unstable training with SGD-VGR when the learing rate goes too large. On the other hands, Dp and DDPNOpt2nd are able to escape from VG with all tested learning rates. Hence, Fig. 6 combines Fig. 12a SGGDVVGR-AA 1r0.1) and Fig. 12c (EKFAC-I10.03, DDPNOpt-Hr0.03, DDPNOpt2nd-1ro.03 for best visualization.
(a)
CE Loss
Sigmoid-Activated Nets
CE Loss Sigmold-Activated Nets
0.25
2,400
SGD SGD-VGR
SGD VGR
EKFAC
0.20
EKFAC
DOPNOpt
DOPNOpt
2.350
DDPNOpt2nd
0.15
DDPNOpt2nd
Trining
2.325
0.10
2,300
2.275
0.05
0.00
2000
Itera tions
Layer
(6)
Activated
0.25
1.0
SCD-VGR
EKFAC
DDPNOpt
(Norm
DOPNOpt
0.15
Trairing
0.10
0.05
0.00
500 1000
1500
2000 2500
3000
3500 4000
lterations
Layer
Figure 10: Vanishing gradient experiment for different losses and nonlinear activation functions.
MMC Sigmold-Activated
MMC Sigmold-Activated
0.25
15.0
Training Loes
12.5
RMSprop DDPNOpt
Adam
Update Norm
0.20
Adam
RMSprop
10.0
DDPNOpt
0.10
7.5
0.00
1000
2000
3000
4000
lteralions
Layer
Figure 11: Vanishing gradient experiment for other optimizers. The legend "DDPNOpr** denotes
DDPNOpt with adaptive diagonal matrix.
10
10
Training Loss
Training Loss
SGD-VGR--r0.5
SGD-VGR-r0.3
EKFAC-IrO.05
SGD-VGR-tr0.1
DDPNOpt-IrO.0g DDPHOpt2 nd-Iroos
SGD-VGR-rr005
Iterations
Iterations
Training Loss
Training Loss
EXFAC-rro.p
EKFAC-IrO.01
DDPNOpt-rro.s
DDPNOpt-Iro.ok
DoPNOst2noirr.03
DDPNOpt2 nd-llo222d 100.01
3000
3000
Iterations
Iteaaioon
Figure 12: Vanishing gradient experiment for different learning rate setups.
18


Reviews:
[{"review_id": "qivdh-iJBu", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nA. Summary:\nThis 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.\nBesides, 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.\nFinally, 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.\n\nB. Strength:\n1. 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.\n2. 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.\n3. 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.\n\nC. Weakness:\n1. 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.\n2. 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.  \n4. 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.\n5. 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. \n\nD. Justification of the score:\nI 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.\n\nE. Expectation for the rebuttal:\nI hope the authors could address my questions in C.weakness and make the paper easier to follow for a broader audience.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JWEvl0RbFG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Updated review\n-----\n-----\n\nGiven 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.\n\n\nInitial review\n----\n----\n\n# Summary\n\nThe 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.\n\n# Reason for score\n\nOverall, 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.\n\n# Pros\n\n* 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.\n* 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.\n* 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.\n\n# Cons\n\n* 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.\n\n# Questions for the authors\n\n* 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?\n* 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?\n* What are the standard deviations for the results in table 3?\n* 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.\n* What is the steepest slope for the memory usage of DDPNOpt in figure 3?\n* How do ADAM, EKFAC and E-MSA keep a constant memory usage as the batch size increases?\n* 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?\n* Figure 4, what does the value of the $V_{xx}$ regularization axis correspond to?\n* 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)?\n* 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)?\n* 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?\n* 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)?\n* How would the behavior of DDPNOpt (using 2nd order terms) be affected by using activations that have zero 2nd derivatives, e.g., ReLu?\n\n# Minor comments and typos\n\n* 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.\n* 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$\n* 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.\n* 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).\n* \"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.\n* 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "I-1rBRF4kEv", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nPositives:\n1) The method seems to mitigate the effect of vanishing gradients \n2) Learns models that can outperform state of the art optimizers as well as other methods based on the same family of approximate DP. \n3) The method seems simple to implement and generalizes commonly used ones depending on the choice of Hessian approximation.\n4) Despite approximations, the approach is more principled then most SOTA heuristics \n5) The effect of state (hidden activations or pre-activations) feedback on vanishing is illustrated very nicely and experiments are neat. \n\nNegatives:\n1) 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. \n\n2) 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.  \n\n3) 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. \n\nMy initial score is positive but I think this feedback should be accounted for the revised version and amendements are made to maintain this score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AU-9AWvYvl", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper draws connections between training neural networks, and trajectory optimization via differentiable dynamic programming (DDP) from optimal control.\n\nThe 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).\n\nThe paper does a good job of presenting this connection, with helpful figures and text to aid the reader.\n\nGiven 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).\n\nThe 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.\n\nThe 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.\n\nFirst, 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.\n\nSecond, 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.\n\nThird, 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?\n\nOverall, 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.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)