Ellipsoidal Trust Region Methods for Neural Network Training
Authors: Leonard Adolphs
Jonas Kohler
Aurelien Lucchi
Venue:  (2020)
Keywords: non-convex
optimization
neural networks
trust-region

Abstract: We investigate the use of ellipsoidal trust region constraints for second-order optimization of neural networks. This approach can be seen as a higher-order counterpart of adaptive gradient methods, which we here show to be interpretable as first-order trust region methods with ellipsoidal constraints. In particular, we show that the preconditioning matrix used in RMSProp and Adam satisfies the necessary conditions for provable convergence of second-order trust region methods with standard worst-case complexities. Furthermore, we run experiments across different neural architectures and datasets to find that the ellipsoidal constraints constantly outperform their spherical counterpart both in terms of number of backpropagations and asymptotic loss value. Finally, we find comparable performance to state-of-the-art first-order methods in terms of backpropagations, but further advances in hardware are needed to render Newton methods competitive in terms of time.

Under review as a conference paper at ICLR 2020
ELLIPSOIDAL TRUST REGION METHODS FOR NEURAL NETWORK TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the use of ellipsoidal trust region constraints for second-order optimization of neural networks. This approach can be seen higher-order counterpart of adaptive gradient methods, which we here show to be interpretable as first-order trust region methods with ellipsoidal constraints. In particular, we show that the preconditioning matrix used in RMSProp and Adam satisfies the necessary conditions for provable convergence of second-order trust region methods with standard worst-case complexities. Furthermore, we run experiments across different neural architectures and datasets to find that the ellipsoidal constraints constantly outperform their spherical counterpart both in terms of number of backpropagations and asymptotic loss value. Finally, we find comparable performance to state-of of- the-art first-order methods in terms of backpropagations, but further advances in hardware are needed to render Newton methods competitive terms of time.
INTRODUCTION
We consider finite-sum optimization problems of the form
min w ERR
L(w)
Σ ((((w,;;
which typically arise in neural network training, e.g. for empirical risk minimization over a set of data points ys) E Rin x Rout loss function and R Rd - Rout represents the neural network mapping parameterized by the concatenation of layers w E TRd, which is non-convex due to its multiplicative nature and potentially non-linear activation functions. We assume that L is lower bounded and twice differentiable, i.c. L E (2( R) and consider finding a first- and second-ordes stationary point w for which [V[(W) || I Eg and Amin (V²L(w)) 2 -CH- Non-convex optimization problems are ubiquitous in machine learning. Among the most prominent examples present-day deep neural networks, that have achieved outstanding results on core tasks such as collaborative filtering (Wang
I.....n. Here, é Rout Rout + R+ is a convex
al. 2015), sentence classification (Kim 2014) and image classification (Krizhevsky et al. 2012).
In the era of big data and deep neural networks, stochastic gradient descent (SGD) is one of the most widely used training algorithms (Bottoul 2010). What makes SGD so attractive is its simplicity and per-iteration cost that are independent of the size of the training set (n) and scale linearly in the dimensionality (d). However, gradient descent is known be inadequate optimize functions that are ill- ill-condttioned (Nesterov, 2013) Shalev-Shward et al. 2017) and thus adaptive gradient methods that employ dynamic, coordinate-wist learning rates based on past gradients includdin Adagrad DDuchi et al.] 2011), RMSprop (Tieleman & Hinton 2012) and Adam (Kingma & Ba 2014)-
become a popular alternative, often providing significant speed-ups over SGD. Yet. there exist no thcoretical proofs that these methods are faster than gradient descent (Li & Orabona 2018).
From a theoretical perspective, Newton methods provide stronger convergence guarantees by appro- priately transforming the gradient in ill-conditioned regions according second-order derivatives. It is precisely this Hessian information that allows regularized Newton methods to enjoy superlinear local convergence as well to provably escape saddle points (Conn et al. 2000). While second-order algorithms have a
history even in the realm neural network training (Hagan & Menhaj 1994 Becker al. 1988), they were mostly considered computationally and memory

---

Under review as a conference paper at ICLR 2020
expensive for practical applications. Yet, the seminal work of Martens (010)) renewed interest for their use in deep learning by proposing efficient Hessian-free methods that only access second- order information via matrix-vector products which can be computed at the cost of an additional backprop-
agation (Pearlmutter) 1994, Schraudolph (002). Among the class of regularized Newton methods, trust region (Conn et al. 2000) and cubie regularization algorithms (Cartis et al. (01T]) are the most principled approaches in the sense that they yield the strongest convergence guarantees. Recently,
stochastic extensions have emerged (Xu al. 2017b] Yao et al., 20188 Kohler & Lucchi 2017
Gratton et al., 2017], which suggest their applicability for deep learning.
We here propose simple modification to make TR methods even more suitable for neural network training. Particularly, we build upon the following alternative view on adaptive gradient methods:
While gradient descent can be interpreted as a spherically constrained first-order TR method, precon- ditioned gradient methods-swe such as Adagrad-cat can be seen as first-order TR methods with ellipsoidal trust region constraint.
This observation is particularly interesting since spherical constraints are blind to the underlying geometry of the problem, but ellipsoids can adapt to local landscape characteristics, thereby allowing for more suitable steps in regions that are ill-conditioned. We will leverage this analogy and investigate the use of the Adagrad and RMSProp preconditioning matrices as ellipsoidal trust region shapes within a stochastic second-order TR algorithm (Xu et al. 2017a Yao et al. 2018). Since no ellipsoid fits all objective functions, our main contribution lies in the identification of adequate matrix- -inuucd
constraints that lead to provable convergence and significant practical speed-ups ups for the specific case of deep learning. On the whole, our contribution is threefold:
We provide a new perspective on adaptive gradient methods that contributes to a better understanding of their inner-workings. Furthermore, empirically find that many neu- ral network problems exhibit diagonally dominated Hessian matrices which suggests the effectivity of diagonal preconditioning. (Section 3)
We investigate the first application of ellipsoidal TR methods for deep learning. In Theorem | we show that the RMSProp matrix can directly be applied as constraint inducing norm in second-order TR algorithms while preserving all convergence guarantees (Theorem 2
Finally, we provide an experimental benchmark across different real-world datasets and architectures. We also compare against adaptive gradient methods and show results in terms of backprogations, epochs, and wall-clock time: a comparison we were not able to find in the literature. (Section 5)
Our main empirical results demonstrate that ellipsoidal constraints prove to be very effective modification of the trust region method in the sense that they constantly outperform the spherical TR method, both in terms of number of backprogations and asymptotic loss value variety of tasks.
2 RELATED WORK
First-order methods The prototypical method for optimizing Eq. (I is SGD (Robbins & Monro 1951). While the practical success of SGD in non-convex optimization unquestioned. the theoretical foundation of this phenomenon is still rather limited. Recent findings suggest the ability of this method to escape saddle points and reach local minima in polynomial time for general non-convex problems, but they either need to artificially add noise to the iterates (Ge et al.. [013]] Lee et al.) 2016) or make an assumption on the inherent noise of vanilla SGD (Daneshmand et al.) 2018). For neural network training, a recent line of research proclaims the effectiveness of SGD, but the results usually
come at the cost of fairly strong assumptions such as heavy overparametrization and Gaussian inputs (Du et al. 2017: Brutzkus & Globerson| 2017 Li & Yuan 2017 Du & Lee| 2018 Allen-Zhu et al.) 2018). Adaptive gradient methods (Duchi et al. 201 Tieleman & Hinton 2012 Kingma & Ba
2014) build on the intuition that larger learning rates for smaller gradient components and smaller learning rates for larger gradient components balance their respective influences and thereby make the methods behave as if they were optimizing a more isotropic surface. Such approaches have first been suggested for neural networks by LeCun et al. (2012). Recently, convergence guarantees for such methods are starting to appear (Ward et al. 2018 Li & Orabonal 2018). However, these are not superior to the O(E,²) 2) worst-cass complexity of standard gradient descent (Cartis et al. 2012b).
2

---

Under review as a conference paper at ICLR 2020
Regularized Newton methods The most principled class of regularized Newton methods are trust region (TR) and adaptive cubic regularization algorithms (ARC) (Conn et al. 2000; Cartis et al.) 2011), which repeatedly optimize a local Taylor model of the objective while making sure that the step does not travel too far such that the model stays accurate. While the former finds first-order stationary
points within 2,,,)), ARC only takes at most D(c,3/)) However, simple modifications the TR framework allow these methods to obtain the same accelerated rate (Curtis et al. 2017). Both methods take at most (cz²)) iterations to find E approximate second-order stationary point (Cartis et al. 2012a). These rates are optimal for second-order Lipschitz continuous functions (Carmon et al.
2017| Cartis et al. 2012a) and they can be retained even when only sub-sampled gradient and Hessian information is used KKhller & Lucchi 2017: Yao et al., 2018 Xu et al., 2b1 Blanchet et al. 2016
Liu et al. 2018; Cartis& & Scheinberg 2017). Furthermore, the involved Hessian information can be computed solely based on fessian-vector products, which are implementable efficiently for neural networks [Pearlmutter] 1994). This makes these methods particularly attractive for deep learning, but the empirical evidence of their applicability is so far very limited. We are only aware of the works of Liu et al. (2018) and Xu et al. (2017a), which report promising first results but these are by no means fully encompassing.
Gauss-Newton methods An interesting line of research proposes to replace the Hessian by (approx- imations of) the generalized-Gauss- Newton matrix (GGN) within Levenherg-Marquaae framework
(LeCun et al. 2012 Martens 2010; Martens & Grosse 2015). These methods have been termed hessian-free since only access to GGN-vector products required. As the GGN matrix is always pos- itive semidefinite, they cannot leverage negative curvature to escape saddles and hence, there exist no second-order convergence guarantees. Furthermore, there are cases in neural network training where the Hessian is better conditioned than the GGN matrix (Mizutani & Dreyfus (200)), Nevertheless, the above works report promising preliminary results, most notably Grosse & Martens (2016) report that K-FAC can be faster than SGD on a small convnet. On the other hand, recent findings report performance at best comparable to SGD on the much larger ResNet architecture (Ma et al. 2019)) Moreover, Xu et al. (2017a) reports many cases where TR and GGN algorithms perform similarly.
This line of work is to be seen as complementary to our approach since it is straight forward to replace the Hessian in the TR framework with the GGN matrix. Furthermore, the preconditioners used in Martens| (2010) and (Chapelle & Erhan (2011), namely diagonal estimates of the empirical Fisher and Fisher matrix, respectively, can directly be used as matrix norms in our ellipsoidal TR framework.
AN ALTERNATIVE VIEW ON ADAPTIVE GRADIENT METHODS
Adaptively preconditioned gradient methods update iterates W w. A, 1/2 gt, where gr a stochastic estimate of V(w,)) and A, is a positive definite symmetric pre-conditioning matrix. In Adagrad, A is the un-centered second moment matrix of the past gradients computed as
Aada,t = G. + +I,
where O, I is the d x identity matrix and G, = [gi, g2.-.... . ge) Building up on the intuition that past gradients might become obsolete in quickly changing non-conver landscapes, RMSprop (and Adam) introduce an exponential weight decay leading the preconditioning matrix
Arma,t == ((1 - G)G (i..,( G[) +I,
(3)
where 3 E 1). In order to save computational efforts, the diagonal versions diag(A and diag(Arms) (Amss) are more commonly applied in practice, which in turn gives rise to coordinate-wise adaptive stepsizes that are enlarged (reduced) in coordinates that have seen past gradient components with smaller (larger) magnitude. In that way, the optimization methods can account for gradients of potentially different scales arising from e.g. different layers of the networks.
3.1 ADAPTIVE PRECONDITIONINS AS ELLIPSOIDAL TRUST REGION
Starting from the fact that adaptive methods employ coordinate- wise stepsizes, one can take a principled view of these methods. Namely, their update steps arise from minimizing first-order
This algorithm is simplified TR method, initially tailored for non-linear least squares problems (Ncedaa Wright 2006)
3

---

Under review as a conference paper at ICLR 2020
Taylor model of the function L within ellipsoidal search space around the current iterate Wt, where the diameter of the ellipsoid along a particular coordinate is implicitly given by n and lig A. Correspondingly, vanilla (S)GD optimizes the same first-order model within a spherical constraint. Fig. | (top) illustrates this effect by showing not only the iterates of GD and Adagrad but also the implicit trust regions within which the local models were optimized at each step Since the models are linear, the constrained minimizer always found on the boundary.
Adagee
Aligedd
Adag ad
Adagot CeggoaaA
56--
10
16.
20
20
Figure 1: Top: Iterates and implicit trust regions of GD and Adagrad three quadratic objectives with diffcrent condition number Bottom: Average log suboptimality over iterations well 90% confidence intervals 30 rums with random initialization
It is well known that GD struggles to progress towards the minimizer of quadratics along low- curvature directions (see e.g., Goh (2017). While this effect is negligible for well-conditioned objectives (Fig. [ left), it leads to drastically slow-down when the problem is ill-conditioned (Fig. [ center). Particularly, once the method has reached the bottom of the valley, it struggles to make progress along the horizontal axis. Here is precisely where the advantage of adaptive stepsize methods comes into play. As illustrated by the dashed lines, Adagrad's 's search space is damped along the direction of high curvature (vertical axis) and elongated along the low curvature direction (horizontal axis). This allows the method to move further horizontally early on to enter the valley with a smaller distance to the optimizer w' along the low curvature direction which accelerates convergence.
Theorem (Preconditioned gradient methods as TR). A preconditioned gradient step
We+1 W. = = -1) A,
(4)
with stepsize Ni > 0, symmetric positive definite preconditioner A. E BRdd and g: * minimizes first-order model around w. E Edd in ellipsoid given by A₁ in the sense that
St == arg min SERS
(s) = L(w.) + + sTg.]
S.L.
|| S T Selglll
Corollary (Rmsprop). The step Syms, = tms gg minimizes first-order Taylor model
around wi in an ellipsoid given by A (Eq. 3 in the sense that
Syms, = arg min SERd
(s) L(w.) + +
|s|| 1/22,
S mel li Tell//lll-1//3
(6)
Equivalent results can be established for Adam using Badam.t == (1 3) k=z gt-k as well as for Adagrad by replacing the matrix Aada into the constraint in Eq. 66 Of course, the update procedure in Eq. (5) is merely reinterpretation of the original preconditioned update, and thus the employed trust region radii are defined implicitly by the current gradient and stepsize.
For illustrative purposes, only plot every other region.
4

---

Under review as a conference paper at ICLR 2020
3.2 DIAGONAL VERSUS FULL PRECONDITIONING
A closer look Fig. | reveals that the first two problems come with level sets that are perfectly axis-aligned, which makes these objectives particularly attractive for diagonal preconditioning. For comparison, the right of Fig. [ we report another quadratic problem instance, where the Hessian no longer zero on the off-diagonals. As can be seen, the interaction between coordinates introduces tilt in the level sets and reduces the superiority of diagonal Adagrad over plain GD. However, using the full preconditioner Ada re-establishes the original speed up. Yet, non-diagonal preconditioning comes the cost of taking the inverse square root of large matrix, which is why this approach has been relatively unexplored (see Agarwal et al. (2018) for a recent exception).
Interestingly, early results by Becker et al. 1988) the curvature structure of neural nets report a strong diagonal dominance of the Hessian matrix (²L(w). This suggests that the loss surface indeed somewhat axis-aligned. However, the reported numbers are only for tiny fera-forward networks of at most 256 parameters. Therefore, we generalize these findings in the following to larger networks. Furthermore, we contrast the diagonal dominance of real Hessian matrices to the expected behavior of random Wigner matrices. Of course, true Hessians do not have i.i.d. entries but the symmetry of Wigner matrices suggests that this baseline not completely off. Furthermore, we also compare Hessians of Ordinary Least Squares problems (OLS) with random inputs. For this
purpose, let A define the ratio of diagonal to overall mass matrix A, i.e. SΛ E, A.. in (Becker et al. 1988)
as
Proposition 1 (Diagonal share of Wigner matrix). For random Gaussiar Wigner matrix W formed as
N(0,of)) i i<j ~~ o2). i=
W. = W
where stands for i.i.d. draws Wigner 1993), the diagonal mass of the expected absolute matrix amounts to
8 [/] =
(8)
1+ (d 1)
Thus, if we suppose the Hessian at any given point w were a random Wigner matrix we would expect the share of diagonal mass to fall with (1/d)) the network grows in size. A similar result can be derived for the large n limit in the case of OLS Hessians.
Proposition 2 (Diagonal share of OLS Hessian). Let X E Bdxa and assume each Xig is generated i..dd with zero-mean finite second moment o² > 0. Then the share of diagonal mass of the expected matrix E | amounts
VR
8g HHwl
/n + (d - 1) 2
Again, we expect the diagonal mass to fall in d and interestingly, empirical simulations suggest that the result of Proposition] 2 holls already in small settings (see Fig D.2) and it is likely that finite n results can be derived when adding assumptions such as Gaussian data. As can seen in Fig. 2 below, even for practical batch size of n 32 the diagonal mass Hh of neural networks stays above both benchmarks when its input is random as well as with real-world data at random initialization, during training and after convergence.
'The argument naturally extends any distribution with positive expected absolute values.
5

---

Under review as a conference paper at ICLR 2020
33
350
ConvNet
MLP
200
100
Wageor
Figure 2: Diagonal mass of neural network Hessian бд relative to (x/li) and 65 H..ll of corresponding dimensionality for random inputs well random initialization, middle and end of training with RMSProp on CIFAR- 1O. Mcan and 95% CI over 10 independent runs.
These findings in line with Becker al. (1988) and suggest that full matrix preconditioning is most probably not worth the additional computational cost for neural networks. Consequently, we diagonal preconditioning for both first- and second-order methods in all of our experiments in Section 5 Further theoretical elaboration of these findings present an interesting direction of future research.
SECOND-ORDER TRUST REGION METHODS
Cubic regularization (Nesterov & Polyak 2006 Cartis 2011) and trust region methods belong to the family of globalized Newton methods. Both frameworks compute parameter updates by optimizing regularized (former) or constrained (latter) second-order Taylor models of the objective around the current iterate W. In particular, in iteration t the update step of the trust region algorithm computed as
1 S ms(s) == L(w:) + g.s + 2
min SER
s.t. ||S||A S.
(10)
where A > O and g: and B, are either ((ww,) and V²L(w,) or suitable approximations. The
matrix A, induces the shape of the constraint set. So far, the common choice for neural networks is
A, == I, Vi which gives rise to spherical trust regions (Xu et al. 201 7a the constrained problem (TO), TR methods overcome the problem that pure Newton steps may be
Liu et al. 2018). By solving
ascending, attracted by saddles or not even computable. See Appendix B for more details.
4.1 CONVERGENCE OF ELLIPSOIDAL TRUST REGION METHODS
Inspired by the success of adaptive gradient methods, we investigate the use their preconditioning matrices norm inducing matrices for second-order TR methods. The crucial condition for con- vergence is that the applied norms are not degenerate during the entire minimization process in the sense that the ellipsoids do not flatten out (or blow up) completely along any given direction. The following definition formalizes this intuition.
Definition (Uniformly equivalent norms). The norms ||w||A, := (wTA, 1/2 induced by sym- metric positive definite matrices A₁ are called uniformly equivalent, if 3μ 2 such that
w |
<
||w]22 & |||w|lA.
Vw E Rd Vt 1,2,
(1I)
We now establish result which shows that the RMSProp ellipsoid is indeed uniformly equivalent.
'In the following only treat TR methods, hut would like to emphasize that the use of matrix induced norms directly he transferred the cubic regularization framework.

---

Under review as a conference paper at ICLR 2020
Lemma 1 (Uniform equivalence), Suppose Igg 2 3 for all w. E IR, 2.... Then there always exists such that the proposed preconditioning matrices Arms,t (Eq.. are uniformly equivalent, i.e. Def. hools. The same holds for the diagonal variant.
Consequently, the ellipsoids Arms,t can directly be applied to any convergent TR framework without losing convergence guarantees (Conn et al. (2000), Theorem 6.6.8) Interestingly, this result cannot be established for t, which reflects the widely known vanishing stepsize problem that arises since squared gradients are continuously added to the preconditioning matrix. At least partially, this effect inspired the development of RMSprop (Tieleman & Hinton 2012) and Adadelta (Zeiler 2012).
Why ellipsoids? There are many sources for ill ill-conditioning in neural networks such as un-centered and correlated inputs (LeCun al.) 2012), saturated hidden units, and different weight scales in different layers (Van Der Smagt & Hirzinger 1998). While the quadratic term of model (TO) accounts for such ill-conditioning to some extent, the spherical constraint is completely blind towards the loss surface. Thus, it is advisable to instead measure distances in norms that reflect the underlying geometry (see Chapter 7.7 in Conn et al. (2000). The ellipsoids we propose are such that they allow for longer steps along coordinates that have seen small gradient components in past and vice versa. Thereby the TR shape is adaptively adjusted to the current region of the non-convex loss landscape. This procedure is not only effective when the iterates are in ill-conditioned neighborhood of minimizer (Figure T). but it also helps to escape elongated plateaus (see autoencoder in Section 5).
4.2 A STOCHASTIC TR FRAMEWORK FOR NEURAL NETWORK TRAINING
Since neural network training often constitutes large-scale learning problem in which the number of datapoints n is high, we here opt for stochastic TR framework in order to circumvent memory issues and reduce the computational complexity. In particular, we adapt the framework of Yao et al. (2018): Xu et al. (2017b) to the case of veraationdeeeetae
norm constraints (Algorithm DT. We -5 _x²²)) worst-case iteration complexity is retained, which is optimal the function is second-order smooth (Cartis er al.) 2012a). Towards this end, we assume that the derivative estimates are sufficiently accurate in the following sense.
prove that the O max { H
Assumption (Sufficiently accurate derivatives). The upproximations of the gradient and Hessian at step satisfy
g+ VL(w:)ll S 8, and |B, VDL(w,)] S0H,
where 0g <
(1-n)ez and 8 & min [1-n)veH 1 for some 0 < < 1-
For finite-sum objectives such as Eq. [ the above condition can be met by random sub-sampling due to classical concentration results for sums of random variables (Xu et al. 2017b Kohler & Lucchi 2017 Tripuraneni et al., 2017). Following these references, we assume access to the function value in each iteration for our theoretical analysis but we note that convergence can be retained even for fully stochastic trust region methods (Gratton et al., 20177; Chen et al.) [0188] Blanchet et al. 2016) and indeed our experiments in Section 5 use sub-sampled function values due to memory constraints.
$ 'Noee that the assumption of bounded batch gradients, i.e. smooth objectives, is common in the analysis of stochastic algorithms (Allen-Zhu 2017 Defazio al. (004 Schmidt al. 2017 Duchi al. 201T).
7

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Stochastic Ellipsoidal Trust Region Method
1: Input: Wy E RR , 1, > 71 > 0, Au > 0
2: for = 0, 1, ..... until convergence do
3: Compute approximations g. and B,, If [g:: S Eg. set g: := 0.
4: Set A, == Arms. or A, == diag (Arms,t) (see Eq. (3).
5: Obtain S, by solving my (s,) approximately.
6: Compute ratio of function over model decrease
Pt f(w,) L(w, s,)
(12)
m2 - (sc)
7: Set
[7A, [1//y
if ps, 1
Ww +
pt
(successful)
D1+1
We+1
if ps.: < n
Ws
otherwise
(unsuccessful)
8: end for
Theorem (Convergence rate of Algorithm 1. Assume that L(w) is second-order smooth with
Lipschitz constants Lg and Lи- Furthermore, let Assumption 7 [and? LindZhold hold. Then Algorithm I finds an Ote EH) first- and second-order stationary point in at most O (max {&g iterations.
-- -1 -3
H f })
EXPERIMENTS
Trust region methods To validate claim that ellipsoidal TR methods yield improved perfor- mance over spherical ones, we run a set of experiments on two image datasets and three types of network architectures. As can be seen in Figure the ellipsoidal TR methods consistently outperform their spherical counterpart the sense that they reach full training accuracy substantially faster on all problems. Moreover, their limit points are in all cases lower than those of the uniform TR method. Interestingly, this makes an actual difference in the image reconstruction quality of autoencoders (see Figure 12). We thus draw the clear conclusion that the ellipsoidal trust region constraints we propose are to be preferred over their spherical counterpart when training neural networks. Both the experimental and architectural details are provided in Appendix C.
ResNei18
MLP
autoencoder
131 Unlber
Uauttmm
0.5
63
771 Adagrud Mbtispppp
6.
Paslio-MNNNST
18 Untiee
TK Aikenaa
-2.0
kggt
Catioom
Undera
T8 K00
90-5ysp
CIPAR-10 Iaptee
64
-62
1000 2003 3000 4100 5000 6300 2006 8000
3.0
0.2
0.4
300
0.2
2.5
1.5
15
200
25
3.0
Figure 3: Log loss over backpropagations. Mean and 95% of runs. Green dotted line indicates 99% acc.
8

---

Under review as a conference paper at ICLR 2020
ResNet18
MLP
Jutomeoder
Adagrid
Adgrel 100rpme
Fasiinn-MNI MNNN-
Adam
SGD
TK R00igme
-110
-1.6
6.4
1.0
1.0
15
of backgeep-aplllla
0.0
CIPAR-I0 I0
logilo50
Mayad RMiipee 805
Adagrad
RMi5pmp
TR 5M55gup
Adam
9CD
2000
4030
6003
0000
backpropagetioos
of backprppigntteee
of ofiictpppogitoo
Figure 4: Log loss over backpropagations. Same setting as Figure 3
See Figure 10 for epoch results.
Benchmark with SGD To put the previous results into context, we also benchmark several state- of-the-art gradient methods. We fix their sample size to 32 (as advocated e.g. in Masters & Luschi (2018) but grid search the stepsize since it is the ratio of these two quantities that effectively determines the level of stochasticity (Jastrzebski et al. 2017). As the TR methods have a larger batch size of 128-512, we report results both in terms of number of backpropagations and epochs for fair comparison. A close look at Figure and I0 (Appendix) indicates that the ellipsoidal TR methods can be slightly superior terms of backprops but at best manage keep pace with first-order methods in terms of epochs. Furthermore, the limit points of both first- and second-ord same order of loss in most experiments. When taking gradient norms into account (plot omitted), we indeed find no spurious local minima and only the autoencoders give rise to saddle points.
methods yield the
6 CONCLUSION
We investigated the use of ellipsoidal trust region constraints for neural networks. We have shown that the RMSProp matrix satisfies the necessary conditions for convergence and our experimental results demonstrate that ellipsoidal TR methods outperform their spherical counterparts significantly. We thus consider the development of further ellipsoids that can potentially adapt even better the loss landscape such e.g. (block-) diagonal hessian approximations (c.g. Bekas et al. (2007)) or approximations of higher order derívatives as an interesting direction of future research.
Yet, the gradient method benchmark indicates that the value of Hessian information for neural network training is limited for mainly three reasons: 1) second-order methods rarely yield better limit points, which suggests that saddles and spurious local minima are not a major obstacle; 2) gradient methods can run on smaller batch sizes which is beneficial in terms epoch and when memory is limited; 3) The per-iteration time complexity is noticeably lower for first-order methods (Figure 11. These observations suggest that advances in hardware and distributed second-order algorithms (c.g.. Osawa et al. (2018); Dünner et al. (2018) will be needed before Newton-type methods can replace (stochastic) gradient methods in deep learning.
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. The case for full-matrix adaptive regularization. arXiv preprint arXiv: 02958, 2018.
We observed weaker performance when running with smaller batch size. We hypothesize that second-order methods extract information of each batch and thus likely to "overfit" small batches in each step.
9

---

Under review as a conference paper at ICLR 2020
Guillaume Alain, Nicolas Le Roux, and Pierre-Antoine Manzagol. Negative eigenvalues of the hessian in deep neural networks. 2018.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods, The Journal of Machine Learning Research, 18(1):8194-8244, 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 181 03962, 2018.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):2112776, 1998.
Sue Becker, Yann Le Cun, et al. Improving the convergence of back-propagation learning with second order methods. In Proceedings of the 1988 connectionist models summer school, pp. 29-37. San Matteo, CA: Morgan Kaufmann, 1988.
Costas Bekas, Effrosyni Kokiopoulou, and Yousef Saad. An estimator for the diagonal of a matrix. Applied numerical mathematics, 57(11-12):214--222 2007.
Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg. Convergence rate analysis of a stochastic trust region method for nonconvex optimization. arXiv preprint arXiv: 1609.07428, 2016.
Leon Bottou. Lcage-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2100, pp. 177-186. Springer, 2010.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-31, 2018.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint arXiv:1702.07900 2017.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. arXiv preprint 17 /606, 2017.
Coralia Cartis and Katya Scheinberg. Global convergence analysis of unconstrained optimization methods based on probabilistic models. Mathematical Programming, pp. 1-39, 2017.
Coralia Cartis, Nicholas IM Gould, and Philippe I. Toinn, Adaptive cubic regularisation methods for unconstrained optimization, part i: motivation, convergence and numerical results. Mathematical Programming, 127(2):245-295, 2011.
Coralia Cartis, Nicholas IM Gould, and Ph L Toint, Complexity bounds for second-order optimality in unconstrained optimization. Journal of Complexity, 28(1):93-108, 2012a.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. How Much Patience to You Have?: Worst-case Perspective Smooth Noncovex Optimization. Science and Technology Facilities Council Swindon, 2012b.
Olivier Chapelle and Dumitru Erhan. Improved preconditioner for hessian free optimization. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, volume 201, 2011.
Ruobing Chen, Matt Menickelly, and Katya Scheinberg. Stochastic optimization using a trust-region method and random models. Mathematical Programming, 169(2):447-487, 2018.
Andrew R Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
Frank E Curtis and Daniel P Robinson. Exploiting negative curvature in deterministic and stochastic optimization. arXiv preprini 703.00//7 2017.
Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi. A trust region algorithm with worst-case iteration complexity of (e3322 )) for nonconvex optimization. Mathematical Program- ming, 162(1-2):1-32. 2017.
10

---

Under review as a conference paper at ICLR 2020
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. arXiv preprint 1003. 2018.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. In Advances in neural information processing systems, pp.
2014.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, pp. 1646-1654 2014.
Simon S Du and Jason Lee. On the power of over-paramettiiaaioon in neural networks with quadratic activation. arXiv preprint arXiv: 180.000000 2018.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time to escape saddle points. Advances Neural Information Processing Systems, pp. 1067-1077 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(u)):2121-2159, 2011. 1.
Colestine Dünner, Aurelien Lucchi, Matilde Gargiani, An Bian, Thomas Hofmann, and Martin Jaggi. A distributed second-order algorithm you can trust. arXiv preprint 1806. 07569, 2018.
Rong Ge. Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points-online stochastic gradient for tensor decomposition. COLT, pp. 797-842, 2015.
Gabriel Goh. Why momentum really works. Distill, 2017. doi: 10.23915/distil.00000 URL ltttp:/dissiil.. pub/ htt///2207//mme/////
Serge Gratton, Clément W Royer, Luís N Vicente, and Zaikun Zhang. Complexity and global rates of trust-region methods based on probabilistic models. IMA Journal of Numerical Analysis, 2017.
Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for convolution layers. In International Conference on Machine Learning, pp. 573-582, 2016.
Martin T Hagan and Mohammad Menhaj. Training feedforward networks with the marquardt algorithm. IEEE transactions on Neural Networks, 5(6):989-993, 1994.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural
networks. science, 31 313(5786):504-0077 2006.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv: 1..6622333 2017.
Yoon Kim. Convolutional neural networks for sentence classification. arXiv preprint arXiv: arXiv:1408.55 1808.5882. 2014.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. In International Conference on Machine Learning. 2017.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105. 2012.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9- Springer, 2012.
Jason D Lee, Max Simchowitz. Michael Jordan, and Benjamin Recht. Gradient descent only converges minimizers. In Conference Learning Theory, pp. 1246-1257, 2016.
11

---

Under review as a conference paper at ICLR 2020
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint /rXiv:/85.008// 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances Neural Information Processing Systems, pp. 597-607, 2017.
Liu Liu, Xuanqing Liu, Cho-Jui Hsich, and Dacheng Tao. Stochastic second-order methods for non-convex optimization with inexact hessian and gradient. arXiv preprint arXiv:1809.0900 0993, 2018.
Linjian Ma, Gabe Montague, Jiayu Ye, Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Inefficiency of k-fac for large batch size training. arXiv preprint arXiv: 19X3:090000022: 2019.
James Martens. Deep learning via hessian-fres frese optimization. In ICML, volume 27, pp. 735-742, 2010.
James Martens. New insights and perspectives the natural gradient method. arXiv preprint arXiv:1412.1 2014.
James Martens and Roger Grosse. Optimizing neural networks with frottcker-factored approximate curvature. In International conference on machine learning, pp. 2408-2417, 2015.
Dominic Masters and Carlo Luschi. Revisiting small batch training for deep neural networks. arXiv preprint arXiv: 07.612, 2018.
Eiji Mizutani and Stuart E Dreyfus. Second-order stagewise backpropagation for hessian-matrix analyses and investigation of negative curvature. Neural Networks, 21(2-3):193-203, 2008
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii Nesterov and Boris T Polyak. Cubie regularization of newton method and its global performance. Mathematical Programming, 108(1):177-205, 2006.
Jorge Nocedal and Stephen J Wright. Numerical optimization, 2nd Edition. Springer, 2006.
Kazuki Osawa, Yohei Tsuji, Yuichiro Ueno, Akira Naruse, Rio Yokota, and Satoshi Matsuoka. Second-order optimization method for large mini-batch: Training resnet-50 on imagenet in 35 epochs. arXiv preprint Stdiv:881..10000 2018.
Razvan Pascanu and Yoshua Bengio. Revisiting natural gradient for deep networks. arXiv preprint 1301::1301.3584, 2013.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zem- ing Lin, Luca Desmaison, Alban aComplexity bounds for second-order optimality in unconstrained optimizationnd Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
Herbert Robbins and Sutton Monro. A stochastic approximation method. In The Annals of Mathe- matical Statistics Volume 22, Number 3. Institute of Mathematical Statistics, 1951.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):83-112 2017.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent.
Neural computation, 1473):773-17733 2002.
Shai Shalev-Shwarte Ohad Shamir, and Shaked Shammah. Failures of gradient-based based deep learning. arXiv preprint S103:170300755 2017.
Trond Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal Numerical Analysis, (03))762-6377, 1983.
12

---

Under review as a conference paper at ICLR 2020
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-mspprop: Divide the gradient by running average its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012.
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. arXiv preprint arXiv: 2017.
Patrick Van Der Smagt and Gerd Hirzinger. Solving the ill-conditioning in neural network learning. In Neural networks: tricks of the trade, pp. 193-206, Springer, 1998.
Hao Wang, Naiyan Wang. and Dit- Rtn Yeung. Collaborative deep learning for recommender systems. In Proceedings of the 2/th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1235-1244, 2015.
Rachel Ward, Xiaoxia Wu, and Leon Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:1806.01 018000000811....11 2018.
Eugene Wigner. Characteristic vectors of bordered matrices with infinite dimensions In The Collected Works of Eugene Paul Wigner, pp. 524-540. Springer, 1993.
Peng Xu, Farbod Roosta- Khosta-Koorasan, and Michael W Mahoney. Second-order optimization for non- convex machine learning: An empirical study, arXiv preprint a7Xi:: 2017a.
Peng Xu, Farbod Roosta-Khorasan Khorasani, and Michael W Mahoney. Newton-type methods for non-convex optimization under inexact hessian information. arXiv preprint arXiv:1708.07164, 201
Zhewei Yao, Peng Xu, Farbod Roosta- Khosta-Khorasani, and Michael W Mahoney. Inexact non-convex newton-type methods. arXiv preprint arXiv: 10X..v//02.009255. 2018.
Matthew D Zeiler. Adadelta: adaptive learning rate method. arXiv preprint arXiv:1212.5700 2012.
13

---

Under review as a conference paper at ICLR 2020
Appendix A: Proofs
A NOTATION
Throughout this work, scalars are denoted by regular lower case letters, vectors by bold lower case letters and matrices as well tensors by bold upper case letters. By -I- denote arbitrary norm. For a symmetric positive definite matrix A we introduce the compact notation where Rd
|w|[a = Aw) 1/2
B EQUIVALENCE OF PRECONDITIONED GRADIENT DESCENT AND FIRST-ORDER TRUST REGION METHODS
Theorem 3 (Theorem restated). preconditioned gradient step
W++1 W. - := A,
(13)
with stepsize Ue > 0, symmetric positive definite preconditioner A. E IRdxd and g: + 0 minimizes a first-order local model around Wi an ellipsoid given by A in the sense that
St == min (s) [(w,) + sTg. s.t. ||s||| n sERd
(14)
Proof. We start the proof by noting that the optimization problem in Eq. [1 constraint satisfies the Slater condition since a strictly feasible point. As a result, any KKT point is feasible minimizer and vice versa.
is convex. For n) > 0
Let L(s, X) denote the Lagrange dual of Eq.
L(s, A) = [(w.) + sTg + (Iei)Ia - Th 11ll8:lla))
(15)
Any point s a KKT point and only if the following system of equations is satisfied
A
V.I(s, ge +
A,S =0
(16)
|s||Ac At
(115)IA,
17 vrl/gell A
(17)
||s||a, mell
A, S 0 A A20
(18)
(19)
For 8; given in Eq. (4) have that
St A,
N70 g.A, g: melgg A nig AA gi
A,
(20)
and thus 17 and hold with equality such that any 2 is feasible. Furthermore,
VgL(s Vf(w.)) ||sell.. A,s:
g
Ttt ne
A,A, g: gi g
g
g: A,
(21)
zero for = |ggell-1 2 As a result, S, is KKT point of the convex problem which proves the assertion.
To illustrate this theoretical result we run gradient descent and Adagrad as well as the two corre- sponding first-order TR method on an ill-conditioned quadratic problem. While the method 1st TR
"Essentially Algorithm with m. based a first order Taylor expansion, i.e. m) (s) in Eq. (14
14

---

Under review as a conference paper at ICLR 2020
optimizes linear model within ball in each iteration, 1st TRaaa optimizes the same model over the ellipsoid given by the Adagrad matrix Aada The results in Figure show that the methods behave very similar to their constant stepsize analogues.
GD
GD
Adeggred
ada
TR
10.1
19
10
200
250
Figure 5: Iterates (left) and log suboptimality (right) of GD, Adagrad and full-featured first-order TR
algorithms of which one (Ist TR) spherically constraint and the other (Ist TRada) uses Auda ellispoid.
C CONVERGENCE OF ELLIPSOIDAL TR METHODS
In order to prove convergence results for ellipsoidal Trust Region methods one must ensure that the applied norms are coherent during the complete minimization process the sense that the ellipsoids do not flatten out (or blow up) completely along any given direction. This intuition is formalized in Assumption which we restate here for the sake of clarity.
I Definition 2 (Definition restated). There exists constant μ such that
| a
||w||2 S p/WllA
Vw E Rd..
(22)
Towards this end, Conn (2000) identify the following sufficient condition on the basis of which we will prove that our proposed ellipsoid Arms is indeed uniformly equivalent under some mild assumptions.
Lemma 2 (Theorem 6.7.1 in Conn et al. (2000)). Suppose that there exists constant 2 such that
mmi (A,) Tmax (Ai) SC
Vt,
(23)
then Definition 7 holds.
Having uniformly equivalent norms is sufficient to prove convergence of ellipsoidal TR methods (se A and Theorem 6.6.8 in (Conn et al., (2000). However, it is so far unknown how the ellipsoidal constraints influence the convergence rate itself. We here prove that the specific ellipsoidal TR method counterpart proposed in
presented in Algorithm ppreservse the rate of its
Yao (2018) (see Theorem 2 below).
First, we show that the proposed Arms. ellipsoid satisfies Definition 1.
Lemma 3 (Lemma l). Suppose ||g 2| < Li for all w. E Rdd 1 1,2,... Then there always exists 0 such that the proposed preconditioning matrices Arma. (Eq. 3 are uniformly equivalent, i.e. Def. holds. The same holds for the diagonal variant.
Proof. The basic building block of our ellipsoid matrix consists of the current and past stochastic gradients G, [gi, ... gr).
We consider Ayms which is built as follows B
'This is generalization of the diagonal variant proposed by Tieleman & Hinton (012)). which precondition
the gradient step by an elementwise division with the square-root of the following estimate 9: = (1 .8) -1* + BV 2
15

---

Under review as a conference paper at ICLR 2020
A Armst = (1 (1-33) 3)G diag(B' (B', 1
3 GT
+ tl.
(24)
From the construction of Armo, it directly follows that for any unit length vector [0]l|/ we have
E
R
u (1- +
=(1 "D dlul2
=(1 - ()) (IDI)) ' (ID))) e||u|β
(25)
2e
which proves the lower bound for Ç 1/c. Now, us consider the upper end of the spectrum of Armet. Towards this end, recall the geometric series expansion
3
Σ k=
8
(26)
1 1 3
t=0
and the fact that GG is sum of exponentially weighted rank-one positive semi-definite matrices of the form g.g.. Thus
Ama (g.g.) Tr(g. Vg. < 1.7
where the latter inequality holds per assumption for any sample size |S]. Combining these facts get that
u GD +d)
=(1 - GDG +< +
=(1 B)
8 ggg u
(27)
5(1 B) 3 2 +c|uu
=(1 g(+1 I +
As result we have that
E E
Aman (Arms,t)
& Amax (Arms,t) < (1 (1-1 g-ttt L3 +
(28)
Finally, achieve uniform equivalence need the r.h.s. of (88 to be bounded by 1/c. This gives rise to a quadratic equation in c, namely
2 +1-11++1) Lige 150
(29)
which holds for any and any 3 E (0, 1) as long as
0 e 5 Li + + L2H))
(30)
Such an c always exists but one needs to choose smaller and smaller values as the upper bound on the gradient norm grows. For example, the usual value 10-8 is valid for all D < 9.9 107. the above arguments naturally extend to the diagonal preconditioner diag( Ayma).
All of
16

---

Under review as a conference paper at ICLR 2020
Second, note that it is necessary to compute the update step by minimizing Eq. 10)) optimality. Instead, suffices to do better than the Cauchy- and Eigenpoint simultancously (Conn) et al. 2000; Yao et al. 2018). We here adapt this assumption for the of iteration dependent norms (compare (Conn et al. 2000) Chapter 6). restate this assumption here
global
Assumption (Approximate model minimization). Each update step St yields at least as much model decrease the Cauchy- and Eigenpoint simultaneously i.e.
me(s:) S me((s)) and mi(se) S mm
(31)
where
St
arg min mi(
and
s F arg min (ouu), lo SA.
(32)
lgll
0Sa5A.
where un is an approximation to the corresponding negative curvature direction, i.e., for some << 1, H.u. Sv
Amin (B.) and Iu. =1
In practice, improving upon the Cauchy point is easily satisfied by any Krylov subspace method such as Conjugate Gradients, which ensures convergence to first order critical points. However, while the Steihaug- Beeihaug-Toint CG solver can exploit negative curvature, it does explicitly search for the most curved eigendirection and hence fails to guarantee m, S m,(s)) Thus more elaborate Krylov descent methods such Lanczos method might have be employed for second-order criticality (See also Appendix B.2 and Conn et al. (2000) Chapter 7).
We restate results from Conn et al. (2000) that precisely quantify the model decrease guaranteed by Assumption
Lemma 4 (Model decrease: Cauchy Point (Theorem 6.3.1. in Conn et al. (0000)). Suppose that s
computed as in Eq. (32). Then
1
ge
ge Igr/
m (0) (s
ge min
Ar
}.
(33)
1
[Be]
Lemma 5 (Model decrease: Eigenpoint (Theorem 6.6.1 in Conn et 2000
Suppose that
(mi) < 0 and s is computed as in Eq. 32 Then
| || [uelli
(0) (s( 2 v Amin (B₂)
A
(34)
We are now ready to prove the final convergence results. Towards this end, we closely follow the line of arguments developed in Yao et al.) (2018). First, restate the following lemma which holds independent of the trust region constraint choice.
Lemma 6 Yao et al. 2018)). Assume that L(w) is second-order smooth with Lipschitz constants Lg and LH. Furthermore, let Assumption 7 hold. Then
1 [|
F(x: + -() F(xx) mi S so (VF(x)) - gi) + _0 ||sc||
2
(35)
Second, we show that any iterate of Algorithm is eventually successful as long as either the gradient norm the smallest eigenvalue are above (below) the critical values eg and
Lemma 7 (Eventually successful iteration ||gell 2 Cg), Assume that L(w) is second-order smooth with Lipschitz constants Lg and Lg. Furthermore, let Assumption and 2 hold and suppose that
g: 2 cg as well as
1- 17
pCg
(1 - n)cg (1 n)
8y
4 Eg. A, min
(36)
I + Lg
12LH 1¹¹ 3rd
then the step St is successful.
17

---

Under review as a conference paper at ICLR 2020
Proof. First, by Assumption 2 Lemma
|gg
Eg
and Lemma
have
Ig
gt
(st) 2
gel min
1+
[B
g+
Eg
g
min
1+
B
gg
(37)
2
Igel min
6g
A
14
[B|
μ
A
= 9
where the last equality uses the above assumed upper bound on A, of Eq. (36 Using this result together with Lemma 6 and the fact that || - s & μÂ, due to Lemma
we find
L(w, + se) [(we) - ms(ss)
(38)
-m (8t)
A1 + 10H 7f 8g
+ 1/2 I 1
1
(39)
A.
c P
8g
On
Lu
2 1
Aip
3
+
A n1²
(40)
Cg
Cg
Cg
1
A.
LH
D7 p
(41)
6g
where the last inequality makes use of the upper bound assumed on 8g. Now, we re-use the result of Lemma 10 in Yao al. (2018), which states that (s A, La L S for 5a
A, min
(1- Il- (1-n)e2
conclude that ( + Lu eg A?) 1t I
1-7 for our assumed
12LH
2
bound on A in Eq. (36) As result, Eq.
38 yields
11-1
which implies that the iteration t is successful.
Lemma 8 (Eventually successful iteration Amin (B:) < -EH), Assume that [(w) is second-order smooth with Lipschitz constants Lg and Lg. Furthermore, let Assumption and hold and suppose that [|g: < Eg and Amin (B,) < -c. If
1- 7
(1- 11) VCH
VCH A
(42)
24 LH
then iteration t is successful.
Proof. First, recall Eq. (35) and note that, since both s; and -s are viable search directions, we can assume s. WVFWW (w.) w.l.o.g... Then
1 S f ||s, 12
1 12 + Lu ||s
L ((w, + st) L(w.) - mw.)))
<
2
2
18

---

Under review as a conference paper at ICLR 2020
Therefore, recalling Eq. (34 well the fact that
|uulle S and |sll22 pl|s:|le
|
ماv due to
Lemma
0
Pr f(we + 8₂) [(w,) (s:)
m4 (s:)
2 # St 11 1/2 L ||s:1l
2 Amin (B,) A μ2
dis s + L ||s:|3
Een1 A n1²
(43)
1 Aip + 1
2 LH 2ip0
2
Aep
VCH
VCH
1 - 1},
where the last second inequality is due to the conditions in Eq. (42) Therefore, Pt v) and the iteration is successful.
Together, these two results allow to establish a lower bound on the trust region radius Ac. Lemma 9. Assume that L(w) is second-order smooth with Lipschitz constants Lug and Lu. Further- more, let Assumption andd] 2 hold. Suppose
8g 4 cg. δн < minf
1 VCH: 1}.
2
then for Algorithm 7 we have
1
cgll
(1 - n)cg
(1 (1-n)cg
(1 -1-17 11)
VCH
A
min
WI 1,2,...
(44)
7
1 L.g"
12
34x²
2/1
I.H
Proof. The proof follows directly from A, 2 11-1/7 well the fact that any step is successful
as soon as A, falls below min
Sal I+
(1-1)eg
(1-n)ea
(1-n) ven
due to Lemma 7 and 8
12L
34
LH
Lemma 10 (Number of successful iterations). Under the same setting as Lemma the number of successful iterations taken by Algorithm iss upper bounded by
C(xu) - -(xx)
Tancel I
Ceh mintez. ez,
17 min (C1, C2). Ci = 1/ min { (TtL, C. C2 yp² min (C2 C2
where C
min-
cgp I+hg'
(1-9)ea 1
(1-nlea CH
(1-9) DEu
3p
2p Lu
Proof. Suppose Algorithm does not terminate iteration 6. Then either ||g:|] 2 eg or Amin (B) s we have
Eh. If [t 2 cg. according to (33 and Lemma
1|g.
m. (st)
gg min
A
+ Heelll
> 5 min!
Cg
Coeg: CHEH}
1+ +Tyg
2 Cieg minn(g,
Similarly, in the second case Amin (B.)= < -hh, from Lemma I and we have
(s) 2 2/ Aman (Bi) 2 Czen min(e, 2.)
2
19

---

Under review as a conference paper at ICLR 2020
Let Jucee denote the number of successful iterations. Since L(w) is monotonically decreasing, have
C ((wo)
L(w*)
((w.) [(W(+1)
Σ [(w,) [(we+1)
TE
-mr(s:)
tETmm
Σ DE
Ceh mig
suce Ceh min
which proves the assertion.
We are now ready to prove the final result. Particularly, given the lower bound on A, established in Lemma 9 we find upper bound on the number of un-successful iterations, which combined with the result of Lemma I0on on the number successful iterations yields the total iteration complexity of Algorithm
Theorem (Theorem 2 restated). Assume that L(w) is second-order smooth with Lipschitz
constants Lg and LH. Furthermore, let Assumption | [nd hold. Then Algorithm finds an Oleg, (H)ffist and second-order stationary point in at most (max {ez²Ept =1 -31 iterations. EH CH
Proof. The result follows by combining the lemmas Pand To in Theorem
of eu al.
72)17a).
D DIAGONAL DOMINANCE IN NEURAL NETWORKS
In the following, we make statements about the diagonal share of random matrices. As E might exist for random variable æ. cannot compute the expectation of the diagonal share but rather of for computing the diagonal share of the expectation of the random matrix in absolute terms. Note that this notion still meaningful. as the average of many non-diagonally dominated matrices with positive entries cannot become diagonally dominated.
D.1 PROOF OF PROPOSITION 1
Proposition 3 (Proposition I restated). For random Gaussian Wigner matrix W formed
N(0, j<j (,) i=
W = W
(45)
where ~ stands for i.i.d. draws Wigner 1993), the diagonal mass of the expected absolute matrix
amounts
(46)
1+ (d 1)
Proof.
E A.
dE W
Sg.W
Σ D E Wa.ll
dE [[] [.1 + d(d 1)E |
do 2/
(47)
do 2 + d(d 1) 2/
d(d- 1)00 2/
do 2/
1)
02 di
20

---

Under review as a conference paper at ICLR 2020
which simplifies to y if the diagonal and off-diagonal elements come from the same Gaussian distribution (01 = 02).
For the sake of simplicity we only consider Gaussian Wigner matrices but the above argument naturally extends to any distribution with positive expected absolute values, i.e. we only exclude the Dirac delta function probability density.
CONV
MLP
40
10.0
20
5.0
0.0
Wigner
start
during
Wigner
start
during
end
Figure 6: Share of diagonal mass of the Hessian ōh relative ow of the corresponding Wigner matrix at random initialization, after 50% iterations and at the end of training with RMSprop on MNIST, Average and 95% confidence interval over 10 runs. See Figure for CIFAR-10 results.
D.2 OLS BASELINE
When considering regression tasks, a direct competitor neural network models is the classical Ordinary Least Squares (OLS) regression, which minimizes quadratic loss over linear model. In this case the Hessian simply amounts to input-covariance matrix Hols : X where We here show that the diagonal share of the expected matrix itself also decays in d, when
X E dx n grows to infinity. However, empirical simulations suggest the validity this result even for much smaller values of n (see Figure D.2) and it is likely that finite results can be derived when adding assumptions such as Gaussian data.
Sc temp IOa
0.9
ViIVE +gg 21/mm
0.7-
0.5
0.3
50
Figure Validity of Proposition in the small n regime for Gaussian data.
Proposition 4 (Proposition restated). Let X axd and assume each Xi,k is generated i.i.d. with zero-mean finite second moment o² O. Then the share of diagonal mass of the expected matrix E [| Hats]] amounts to
restatted,
8gq
11000
(48)
Vn + (d 1)x
21

---

Under review as a conference paper at ICLR 2020
Proof.
Ex=1 k=
E x
Σ 1= E (H
0g Ha.l
Σ k= Ei=l E (Hob))..1)
k= 21=1 1=1
E
Ei= xx,11
(49)
E 1=1 E [x]
4 2i=1
+ d( d 1)E 1> X x
Where used the fact that all & are iid. variables. Per assumption, we have E [x]]]] of, vi. Furthermore, the products X;, X are i.d with expectation and variance of. By the central limit theorem
NN
x Xi, - 7
Vn
in law, with Z -V(0,, since E [ ! due the independence assumption. Then E implies that
EE xx,2)
- o²
[/ 112112R)
E(IZN|/RR) S 80/1/ This
E ((ZZN) - E( V 2 0
As a result, we have that in the limit of large n
dno
1
Vn
(50)
dno² + d(d-d11)))) - (/ld-1)vi/ / 2202
14 (d-1)
(d-
2
Vn
Appendix B: Background on second-order optimization
A NEWTON'S METHOD
The canonical second-orde method Newton's methods. This algorithm uses the inverse Hessian as scaling matrix and thus has updates of the form
W++1 = Wt -'[(ww)-\V[(v))
(51)
which is equivalent to optimizing the local quadratic model
my (w:) == [(w)) + V[((w))s+ 1 V L(w:)s
(52)
2 to first-order stationarity. Using curvature information to rescale the steepest descent direction gives Newton's 's method the useful property of being linearly scale invariant. This gives rise to problem independent local convergence rate that is super-linear and even quadratic in the case of Lipschitz continuous Hessians (see Nocedal & Wright (2006) Theorem 3.5), whereas gradient descent at best achieves linear local convergence (Nesterov) 2013).
However, there are certain drawbacks associated with applying classical Newton's 's method. First of all, the Hessian matrix may be singular and thus not invertible. Secondly, even if invertible the local quadratic model (Eq. 52) that is minimized in each NM iteration may simply be an inadequate approximation of the true objective. As a result, the Newton step is not necessarily a descent step. diverge. Finally, the cost of forming and inverting the Hessian sum up to Ondd d3) and are thus prohibitively high for applications in large dimensional problems.
may hence approximate arbitrary critical points (including local maxima)
22

---

Under review as a conference paper at ICLR 2020
B
TRUST REGION METHODS
B.1 OUTER ITERATIONS
Trust region methods are among the most principled approaches to overcome the above mentioned issues. These methods also construct a quadratic model m, but constrain the subproblem in such way that the stepsize restricted to stay within a certain radius A within which the model is trusted to be sufficiently adequate
1 min ms(s) [(wi) V 1s ((W)) s.t. ||s|| S A..
(53)
SER
Hence, contrary line-search methods this approach finds the step s; and its length ||s||| si- multaneossly by optimizing (53). Subsequently the actual decrease [(w.) L(w; 8.) is compared to predicted decrease m²( (s;) and the step only accepted if the ratio (s:)) exceeds some predefined success threshold 7 > 0.
p: L(w,) [(w, + st)/(m,(0) Furthermore, the trust region radius is decreased whenever p falls below 171 and it is increased whenever p exceeds the "very successful" threshold 1720. Thereby, the algorithm adaptively measures the accuracy of the second-order Taylor model which may change drastically over the parameter space depending on the behaviour of the higher-order derivatives and adapts the effective length along which the model is trusted accordingly. See Conn et al. (2000) for more details.
As consequence, the plain Newton step SN.t (V) VL, is only taken if it lies within the trust region radius and yields a certain amount of decrease the objective value. Since many functions look somehow quadratic close a minimizer the radius can be shown to grow asymptotically under mild assumptions such that eventually full Newton steps are taken in every iteration which retains the local quadratic convergence (Conn al. 2000).
10
W)
MC
10
0.
-35
-05-
-19
-10
-55
-30
-2
Figure 8: Level sets the non-convex, cocrcive objective function f(w) 0.5w + 0.25wf 0.5wf. Newton's 's Method makes local quadratic model (blue dashed lines) and steps to its critical point. It may be thus be ascending (left) attracted by saddle point (right). TR methods relieve this issue by stepping to the minimizer of that model within certain region (green dashed line).
B.2 SUBPROBLEM SOLVER
Interestingly, there is no need to optimize Eq. (53) to global optimality to retain the remarkable global convergence properties of TR algorithms. Instead, it suffices do better than the Cauchy- and Eigenpoin simultaneously. One popular approach is to minimize m²(s) in nested Krylov subspaces. These subspaces naturally include the gradient direction well increasingly accurate estimates of the leading eigendirection
span Bigr, Big..... B(g+}
(54)
until (for example) the stopping criterion
[mm((s))]l [V[(w)
[V((w)))), Æк < 1, 1
(55)
Note that the second-order Taylor models assume constant curvature. which the model minimizers along the gradient and the eigendirection associated with its smallest eigenvalue, respectively.
23

---

Under review as a conference paper at ICLR 2020
is met, which requires increased accuracy the underlying trust region algorithm approaches criticality. Conjugate gradients and Lanczos method are two iterative routines that implicitly build up conjugate and orthogonal basis for such a Krylov space respectively and they converge linearly on quadratic objectives with a square-root dependency on the condition number of the Hessian (Conn) et al., (000). We here employ the preconditionied Steihaug-Toiie CG method (Steihaug 1983) in order to cope with possible boundary solutions of (53) but similar techniques exist for the Lanczos solver well for which we also provide code. As preconditioning matrix for CG we use the same matrix as for the ellipsoidal constraint.
C DAMPED (GAUSS-) NEWTON METHODS
An alternative approach to actively constraining the region within which the model is trusted is to instead penalize the step norm in each iteration in Lagrangian manner. This is done by so-called damped Newton methods that add a À >> 0 multiple of the identity matrix to the second-order term in the model, which leads to the update step
ms(s) [(w,) + V.((W)) (V Al)s SERd
min
2
(56)
= [(w:) + V.((w) L + \||s||.
This can also be solved hessian-free by conjugate gradients (or other Krylov subspace methods). The penalty parameter À is acting inversely to the trust region radius A and it is often updated accordingly, Such algorithms are commonly known as Weveenbrrg-Marquare algorithms and they were originally tailored towards solving non-linear least squares problems (Nocedal & Wright 2006) but they have been proposed for neural network training already early on (Hagan Menhaj
1994).
(w) in 56) with the Generalized Gauss Newton matrix (Martens) 2010, Chapelle Erhan 2011) or an approximation of the latter (Martens & Grosse 2015). This matrix constitutes the first part of the well-known Gauss-Newton decomposition
Many algorithms in the existing literature replace the use of V²(((,)
a n Σ (OOONOVIИ
v26()=
=
+
(((O)))))))
(57)
ACGN
where 1' and 1" are the first and second derivative of I Rout -> R+ assuming that out 1 (binary classification and regression task) for simplicity here.
It is interesting to note that the GGN matrix ACGN of neural networks is equivalent to the Fisher
matrix used in natural gradient descent (Amari) 1998) in many cases like linear activation function and squared error well sigmoid and cross-entropy softmax and negative log-likelihood for
which the extended Gauss-Newton defined (Pascanu & Bengio 2013). As can be seen in (57) d). As a result, there exist no second-orded convergence guarantees for such methods on general non-convex problems. On the other end of the spectrum, the GGN also drops possibly positive terms from the Hessian (see 57
the matrix AGGN is positive semidefinite (and low rank if
Hence it not guaranteed to be an upper bound on the latter in the PSD sense. Essentially, GGN approximations assume that the network piece-wise linear and thus the GGN and Hessian matrices only coincide in the case of linear and ReLU activations or non-curved loss functions. For any other activation the GGN matrix may approximate the Hessian only asymptotically and if the ((()+()) terms in 57 go to zero for all i E {1...., n). In lonelinear least squares such problems are called zero-residual problems and GN methods can be shown have quadratic local convergence there. In any other case the convergence rate does not exceed the linear local convergence bound of gradient descent. In practice however there are cases where deep neural nets do show negative curvature the neighborhood of minimizer [Bottou et al. 2018) (118).Finall Finally, Dauphin al. (2014) propose the use of the absolute Hessian instead of the GGN matrix a framework similar to 56 This method has been termed saddle-fres free Newton even though its manifold of attraction to given saddle is non-empty
It is the same that for GD, which renders the method unable to escape e.g. when initialized right on saddle point. To be fair, the manifold of attraction for GD constitutes measure zero set (Lee al. 2016).
24

---

Under review as a conference paper at ICLR 2020
Wach
W.
15
05
30-
0.-
-15
-05
-10
-10 -2
Figure 9: Both, the GGN method and saddle-free Newton method make positive definite quadratic model around the current iterate and thereby overcome the abstractedness of pure Newton towards the saddle (compare Figure B). However, (i) none of these methods can escape the saddle once they are in the gradient manifold of attraction and (ii) reported in Mizutani & Dreytus (2008) the GN matrix can be significantly less well conditioned than the absolute Hessian (here KGN 49' 487 7544 and R| 1.03 so we had add a damping factor of X = 0.1 to make the GN step fit the plot.
C.I COMPARISON TO TRUST REGION
Contrary to TR methods, the Levenberg-Marquarde methods never take plain Newton steps since the regularization is always on (A > 0). Furthermore, if positive-definite Hessian approximation like the Generalized Gauss Newton matrix used, this algorithm is not capable of exploiting negative curvature and there are cases in neural network training where the Hessian is much better conditioned
than the believe that positive-definiteness is desirable feature (Martens 2010 Chapelle & Erhan 2011), want to point out that following negative curvature directions is necessarily needed to escape saddle points and it also be meaningful to follow directions of negative eigenvalue À outside saddle since they guarantee ([A|))) progress, whereas a gradient descent step yields at least f progress (both under certain stepsize conditions) and one cannot conclude a-priori which one better in general (Curtis & Robinson 2017 Alain et al. 2018). Despite these theoretical considerations, many methods based on GGN matrices have been applied to neural network training (see Martens (2014) and references therein) and particularly the hessian-free implementations of (Martens) 2010
matrix (Mizutani & Dreyfus 2008) (also see Figure 9). While some scholars
Chapelle & Erhan 2011) I can implemented very cheaply (Schraudolph) 2002).
D USING HESSIAN INFORMATION IN NEURAL NETWORKS
While many theoretical arguments suggest the superiority of regularized Newton methods gradient based algorithms, several practical considerations cast doubt on this theoretical superiority when comes neural network training. Answers to the following questions are particularly unclear: Are saddles even an issue in deep learning? Is superlinear local convergence a desirable feature in machine learning applications (test error)? Are second-order methods more "vulnerable" to sabblingling noise? Do worst-case iteration complexities even matter in real-world settings? As result, the value of Hessian information neural network training somewhat unclear a-priori and so far a conclusive empirical study is still missing.
Our empirical findings indicate that the net value of Hessian information for neural network training is indeed somewhat limited for mainly three reasons: 1) second-order methods rarely yield better limit points, which suggests that saddles and spurious local minima are not a major obstacle; 2) gradient methods can indeed run smaller batch sizes which is beneficial in terms of epoch and when memory is limited: 3) The per-iteration time complexity is noticeably lower for first-order methods. In summary, these observations suggest that advances in hardware and distributed second-orde order algorithms (e.g., [Osaw et al. (2018); Dünner et al.] (2018)) will be needed before Newton-type methods can replace (stochastic) gradient methods in deep learning.
25

---

Under review as a conference paper at ICLR 2020
Appendix C: Experiment details
A
EXPERIMENTAL RESULTS
A.1
ELLIPSOIDAL TRUST REGION VS. FIRST-ORDER OPTIMIZER
ResNet18
Fully-Connese
Autoencoder
5G2
CIFAR 10 Inshan
Adagne
50D MO0LAy
-80
110
Pashion-MNIS. (eglim)
50
180
150
200
250
300
353
15
36
48 50
70
8
Figure 10: Experiment comparing TR and gradient methods in terms of epochs. Average log loss as well as 95% confidence interval shown.
ResNet18
Fully-Connectoe
Autoencoder
Adugnd BotSprup
Advyrid 108ipeus
CIFAR- 10 2gthmo
2012
5022
B345gmpppppppp
90d5pmp
Adagred $20
-02
Lissc
Fashion- -NIST 2000
Anagred BM4
Adagred
0.2
R005pmu
S3D
1930 1582 280 (018 238 2081 USB
340
25
125
Figure 11: Experiment comparing TR and gradient methods in terms of wall-clock time. Average log loss as well as 95% confidence interval shown. The advantage of extremely low-iteration costs of first-order methods is particularly notable in the ResNet18 architecture due to the large network size.
B FURTHER EXPERIMENT DETAILS
B. DEFAULT PARAMETERS, ARCIITECTURES AND DATASETS
Parameters Table rrpporss the default parameters we consider. Only for the larger ResNet18 on CIFAR-10, 10, adapted the batch size 128 due to memory constraints.
26

---

Under review as a conference paper at ICLR 2020
[S0]
Ao
A max
7/1
7/2
71
02
RK (krylov tol.)
TRuii
512
10
10
10-4
0.95
1.1
1.5
0.1
TRada
512
10 44
10
10
0.95
1.1
1.5
0.1
TR
512
10-1
10
10-4
0.95
1.1
1.75
0.1
Table 1: Default parameters
We use real-world datasets for image classification, namely CIFAR-10 and Fashion- M While Fashion- MiSSS consists of greyscale 28 x 28 images, CIFAR-10 are colored images size 32 Both datasets have fixed training-test split consisting of 60,000 and 10,000 images, respectively.
Datasets
Network architectures The MLP architectures are simple. For MNIST and Fashion-MNiIs we 784 128 10 network with tanh activations and cross entropy loss. The networks has 101'770 parameters. For the CIFAR-IE 10 MLP we use 3072 128 128 10 architecture also with tanh activations and cross entropy loss. This network has 410'880 parameters.
The Rashion-MNISS autoencoder has the same architecture as the one used in [inntoon Salakhutdinov (2006); Xu al. (2017a); Martens (2010): |Mrtenns & Grossel (2015). The encoder structure is 30 and the decoder is mirrored. Sigmoid activations are used in all but the central layer. The reconstructed images fed pixelwise into binary cross entropy loss. The network has total of 2' 8'833'00 000 parameters. The CIFAR-10 autoencoder is taken from the implementation of https://github...
784 1000 - 500 250
For the ResNet18, we used the implementation from torchvision for CIFAR-16 10 as well as mod- ification of for Fashion-MNN MNIST that adapts the first convolution account for the single input channel.
In all our experiments each method was run on one Tesla P100 GPU using the PyTorch (Paszke
et al. 2017) library.
B.2
RECONSTRUCTED IMAGES FROM AUTOENCODERS
Original
SGD
Adagrad
Rmsprop
TR Uniform
TR Adagrad
TR RMSprop
0
/
2
3
3
6
7
8
9
Figure 12: Original and reconstructed MNIST digits (left), Mishion-MNIST items (middle), and CIFAR-10 classes (right) for different optimization methods after convergence.
Both datasets accessed from htaph///www...ooooooooo////////e
27


Reviews:
[{"review_id": "SklwP8PbcS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "In this paper, the authors investigate the use of ellipsoidal trust region constraints for second order optimization. The authors first show that adaptive gradient methods can be viewed as first-order trust region methods with ellipsoid constraints. The authors then show that the preconditioning matrix of RMSProp and Adam can be used as norm inducing matrices for second order trust region methods. This ellipsoidal trust region method is empirically compared with first order gradient methods and spherical second order trust region methods.\n\nOverall the paper is nicely written and very easy to read. The ideas are interesting. However, I have a number of concerns/questions about the work, that I list below.\n\n1. Why is the preconditioning matrix of RMSProp/Adam a reasonable norm inducing matrix? One can show that the empirical Fisher is not an accurate curvature matrix in general, and so there is no reason to believe this would in fact enforce the proper ellipsoidal trust region for the method? See for example: https://arxiv.org/pdf/1905.12558.pdf.\n\n2. I am also not convinced that Figure 2 actually shows that the curvature matrix is diagonally dominant. How do I interpret a value of 40 or 50 for this metric, and why does it imply that it is diagonally dominant?\n\n3. The experiments also do not look very convincing to me. How sensitive is the algorithm to the hyperparameters like lambda1 and lambda2? I am also a bit confused about why different batch sizes were used for the first order gradient methods and the second order TR methods? The method overall doesn't seem to be able to match first order gradient methods, and it is not clear whether this is because of using the RMSProp/Adam preconditioner as a curvature matrix.\n\nGiven these concerns, I consider this paper to be borderline. I am happy to have a discussion with the authors and the other reviewers and change my score however.\n\n=========================================\n\nEdit after rebuttal:\nI thank the reviewers for their response. While the updated paper has certainly improved, I think the paper still requires a much more thorough experimental evaluation. I am sticking to my score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1e970N2Fr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes ellipsoidal trust region methods for optimization on neural networks. This approach is motivated by the adaptive gradient methods and classical trust region methods. The idea of the design is reasonable, but the theoretical and empirical results are not strong. I can not support acceptance for current version.\n\nMajor comments:\n\n1. Section 4.2 says “Algorithm 1 with A_rms ellipsoids converges with the classical rate O(\\epsilon^{-2}, \\epsilon^{-3}) thanks to Proposition 2 above and Theorem 6.6.8 in Conn et al.  (2000).” I have two questions about this statement.\n\na) What is (\\epsilon^{-2}, \\epsilon^{-3})? Some subscript or min/max notation looks missing.\n\nb) I have checked Theorem 6.6.8 in Conn et al. (2000). It only shows the limit point of the sequence of iterates is a second order critical point. How to obtain the convergence rate of Algorithm 1 seems not directly. I hope the authors provide detailed derivation and present Theorem 6.6.8 here (Maybe the version of the book I have seen is not identical to yours).\n\n2. Is there any stop criterion of the sub-problem solver? How the precision of the sub-problem affects the global convergence rate?\n\n3. The experimental section only reports “log-loss”, which is not enough to deep learning applications. It would be interesting to validate weather the proposed method achieves lower test error than baselines.\n\n\nMinor comments:\n\n1. The values of kappa in the second and the third sub-figures of Figure 1 should be different.\n\n2. The box of Proposition 3 is spited into page 14 and 15.\n\n3. Equation (37) is too long and does not fit within the margins.\n\n===================================\n\nThe authors have provided detailed derivation of the key theorem. I decide to raise my rating to 3. \n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byg1zRwCFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "My understanding is that the paper does not claim to deliver some great results here and now but instead suggest a promising direction (\"that ellipsoidal constraints prove to be a very effective\nmodification of the trust region method in the sense that they constantly outperform the spherical TR\nmethod, both in terms of number of backpropagations and asymptotic loss value on a variety of tasks\"). \n\nI should say that I am not confident about my review. I believe that the authors were careful in phrasing their contribution and provided some supporting material but the wall-clock time results on resnets are too bad to envision any practical application (\"advances in hardware will be needed\"). It would not be a problem if the paper were the first to deal with second-order methods. However, the niche of second-order methods attempting to beat first order methods is not empty and one of the main exit plans consists in showing better wall-clock time convergence, something which is  obviously very hard.\n\nMinor notes:\nbackprogations -> backpropagations\n\n--- \nUpdate: I didn't change my score. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper interprets adaptive gradient methods as trust region methods, and then extends the trust regions to axis-aligned ellipsoids determined by the approximate curvature. It's fairly natural to try to extend the algorithms in this way, but the paper doesn't show much evidence that this is actually effective. (The experiments show an improvement only in terms of iterations, which doesn't account for the computational cost or the increased batch size; there doesn't seem to be an improvement in terms of epochs.) I suspect the second-order version might also lose some of the online convex optimization guarantees of the original methods, raising the question of whether the trust-region interpretation really captures the benefits of the original methods. The reviewers recommend rejection (even after discussion) because they are unsatisfied with the experiments; I agree with their assessment.

Decision: Reject