Adaptive norms for deep learning with regularized Newton methods
Authors: Jonas K Kohler
Leonard Adolphs
Aurelien Lucchi
Venue:  (2021)
Keywords: Stochastic Optimization
Non-convex Optimization
Deep Learning
Adaptive methods
Newton methods
Second-order optimization

Abstract: We investigate the use of regularized Newton methods with adaptive norms for optimizing neural networks. This approach can be seen as a second-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 prove 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 on general non-convex objectives. 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 computational time.

Under review as a conference paper at ICLR 2021
ADAPTIVE NORMS FOR DEEP LEARNING WITH REGULARIZED NEWTON METHODS
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the use of regularized Newton methods with adaptive norms for optimizing neural networks. This approach can be seen as a second-order coun- terpart of adaptive gradient methods, which we here show be interpretable first-order trust region methods with ellipsoidal constraints. In particular, we prove 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 on general non-convex objectives. 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 terms backpropagattons, but further advances in hardware needed render Newton methods competitive in terms of computational time.
INTRODUCTION
We consider finite-sum optimization problems of the form
min WEB4
L(w)
Σ (([(w,x,))))
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 Rin x R + Rott represents the neural network mapping parameterized by the concatenation of the weight layers w E Rd, 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 C² (RRd,, R) and consider finding a first- and second-order stationary point w for which [[V[(W)]] S cy and Amin (V2)(w)) 2 -CH-
I.....n. Here, E: Rout Rour + R+ is a convex
In the of deep neural networks, stochastic gradient descent (SGD) is one of the most widely used training algorithms (Bottou] 2010). What makes SGD so attractive is its simplicity and per-iteration cost that is independent of the size of the training set (n) and scale linearly in the dimensionality (d). However, gradient descent is known to be inadequate to optimize functions that are ill-conditioned (Nesterov 2013) Shalev-Shwartz et al.) (017)) and thus adaptive gradient methods that employ
dynamic, coordinate-wise learning rates based on past gradients-includng Adagrad (Duchi et al.)
201T, RMSprop (Tieleman & Hinton| 2012) and Adam (Kingma & Ba 2014 have become
popular alternative, often providing significant speed-ups over SGD.
From a theoretical perspective, Newton methods provide stronger convergence guarantees by appro- priately transforming the gradient in ill-conditioned regions according to second-order derivatives. It precisely this Hessian information that allows regularized Newton methods to enjoy superlinear local convergence as well as to provably escape saddle points (Conn et al. 2000). While second-order algorithms have long-stand standing history even in the realm neural network training (Hagan & Menhaj 1994. Becker et al. 1988), they were mostly considered as too computationally and memory expensive for practical applications, Yet, the seminal work of Martens (2010) renewed interest for their use in deep learning by proposing efficient Hessian-free methods that only access second-orde information via matrix vector products which can be computed at the cost of an additional backprop- agation (Pearlmutter) 1994 (chraadolphh 2002). Among the class of regularized Newton methods,

---

Under review as a conference paper at ICLR 2021
trust region (Conn et al. 2000) and cubic regularization algorithms (Cartis et al. 2011] are the most principled approaches in the sense that they yield the strongest convergence guarantees. Recently, stochastic extensions have emerged (Xu et al., 2017b; Yao et al.) 2018 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 spherically constrained first-order TR method, precon- ditioned gradient methods-such as Adagrad-can be seen as firsl-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 the identification of adequate matrix-induces constraints that lead to provable convergence and significant practical speed-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-working
We investigate the first application of ellipsoidal TR methods for deep learning. 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 I.
Finally, we provide an experimental benchmark across different real-world datasets and architectures (Section 5). We compare second-order methods also to adaptive gradient methods and show results in terms of backpropagations, epochs, and wall-clock time; comparison we were not able to find in the literature.
Our main empirical results demonstrate that ellipsoidal constraints prove to be a 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 on a variety of tasks.
2 RELATED WORK
First-order methods The prototypical method for optimizing Eq. ① is SGD (Robbins & Monro 195I). The practical success of SGD in non-convex optimization is unquestioned and theoretical explanations of this phenomenon are starting to appear. Recent findings suggest the ability of this method to escape saddle points and reach local minima in polynomial time, but they either need to artificially add noise to the iterates (Ge et al. 2015 Lee al. 2016) or make assumption on the inherent noise of SGD (Daneshmand et al. 2018). For neural networks, a recent line of research proclaims the effectiveness of SGD, but the results come the cost of strong assumptions such as heavy prrmettratti and Gaussian inputs (Du et al. 2017 Brutzkus & Globerson 2017 Li &
Yuan 2017 Du & Lee 20188 Allen-Zhu et al. 2018). Adaptive gradient methods (Duchi et al. 2011 Tieleman & Hinton, 2012; Kingma & Ba 2014) build on the intuition that larger (smaller) learning
rates for smaller (larger) gradient components balance their respective influences and thereby the methods behave as if optimizing a more isotropic surface. Such approaches have first been suggested for neural nets by LeCun et al. (2012) and convergence guarantees are starting to appear (Ward et al. 2018 Li & Orabonal 2018). However, these are not superior to the O 2(²))) worst-case complexity of standard gradient descent (Cartis et al. 2012b).
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. 201T), 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 O ARC only takes at most O(e, 3/2) However, simple modifications to the TR framework allow these methods to obtain the same accelerated rate (Curtis al.) 2017). Both methods
2

---

Under review as a conference paper at ICLR 2021
take at most (c2 iterations to find E approximate second-order stationary point (Cartis et al. 2012a). These rates are optimal for second-ordet Lipschitz continuous functions (Carmon et al. 2017ICartio et al. 2012a) and they can be retained even when only sub- sab-sad gradient and Hessian information is used (Kohler & Lucchi, 2017, Yao et al., 2018 Xu et al., 2017b] Blanchht et al. 2016 be computed solely based
Liu et al. 2018). Furthermore, the involved Hessian information on Hessian-vector products, which are implementable very efficiently (Pearlmutter, 1994). This makes these methods particularly attractive for deep learning, but the empirical evidence of their applicability is rather limited. We are only aware of the works of Liu et al. (2018) and Xu et al. (2017a), which report promising first results but are by no means fully encompassing.
Gauss-Newton methods An interesting line of research proposes replace the Hessian by (approx- imations of) the generalized Gannse----au----aa Newston matrix (GGN) within a Levenberg -aabbbrr-aauurrrtt framework
(LeCun et al. 2012; Martens) 2010; Martens & Grosse 2015). As the GGN matrix is always positive semidefinite these methods cannot leverage negative curvature to escape saddles and hence, there exist no second-order convergence guarantees. Furthermore, there cases in neural networks where the Hessian is better conditioned than the GGN matrix (Mizutani & Dreyfus (008), Nevertheless, the above works report promising preliminary results, most notably Grosse & Martens (2016) find that K-FAC can be faster than SGD on a small convnet. On the other hand, recent findings report performance at best comparable SGD on the much larger ResNet architecture (Ma al.j (201)). Moreover, Xu et al. (2017a) reports many cases where TR and GGN algorithms perform similarly. This line work can be seen as complementary to our approach since it is straightforward to replace the Hessian in the TR framework with the GGN matrix. Furthermore, the preconditioners used in Martens (2010) and [Chapelle& & Erhan (201T), namely diagonal estimates of the empirical Fisher and Fisher matrix, respectively, can directly be used as matrix norms in our ellipsoidal TR framework.
3 AN ALTERNATIVE VIEW ON ADAPTIVE GRADIENT METHODS
Adaptively preconditioned gradient methods update iterates Wt-1 w, n, 1/2 is a stochastic estimate of V ((w)) and A, is a positive definite symmetric pre-conditioning matrix. In Adagrad, Anda,t is the un-centered second moment matrix of the past gradients computed as
7A-,11185 gi, where gr
Aada,t = G. + +I,
where e O, I is the d x identity matrix and G, = [g), ....... Be] Building up on the intuition that past gradients might become obsolete in quickly changing non-convex landscapes, RMSprop (and Adam) introduce an exponential weight decay leading the preconditioning matrix
Arme,t == ((1- - G)G, diag(8' 30) G[) +I,
(3)
where 3 E (0. In order to save computational efforts, the diagonal versions diag(A Andd)) and diag( dlag(Arms)) (rms)) 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 a smaller (larger) magnitude.
3.1 ADAPTIVE PRECONDITIONING AS ELLIPSOIDAL TRUST REGION
Starting from the fact that adaptive methods employ coordinate-wise stepsizes, one can take principled view on these methods. Namely, their update steps arise from minimizing a first-order Taylor model of the function L within an ellipsoidal search space around the current iterate W,, where the diameter of the cllipsoid along a particular coordinate is implicitly given by 7), and ||ge و Correspondingly, vanilla (S)GD optimizes the same first-order model within a spherical constraint. Figure (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
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 a drastic slow-down when the problem ill-conditioned (Fig.) T
'This algorithm a simplified TR method, initially tailored for non-lincar least squares problems NNcedal
& Wriight 2006)
"We only plot every other trust region. Since the models are linear, the minimizer is always on the boundary.
3

---

Under review as a conference paper at ICLR 2021
60
Adherad
60
Al1y31
157
Athyal
39.
44-
15.
08
13
245
150
180
254
20
K. 20
20
Figure 1: Top: Iterates and implicit trust regions of GD and Adagrad quadratic objectives with different condition number x. Bottom: Average log suboptimality over iterations well as 90% confidence intervals of 30 runs with random initialization
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 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 to enter the valley with smaller distance to the optimizer w along the low curvature direction which accelerates convergence.
Let us now formally establish the result that allows to re-interpret adaptive gradient methods from the trust region perspective introduced above.
Lemma (Preconditioned gradient methods as TR). A preconditioned gradient step
We+1 W. = -1; A, A 'g.
(4)
with stepsize πt symmetric positive definite preconditioner A. BRdxd and g: * minimizes first-order model around w, E Rd in an ellipsoid given by A₁ in the sense that
S = arg min SERV
(s) L(w.) + sTg.
s.t.
||s||A. S MllBIlA,
Corollary (Rmsprop). The step Syms, =
rm minimizes a first-order Taylor model
11/2
around we in an ellipsoid given by t (Eq. 3 in the sense that
1/2
Srms, arg min BERd
[m] (s) L(w:) + sTg.] s.1.
||s||| rma.
Selllg: A 1/2
A,
(6)
Equivalent results can be established for Adam using Badom.t Adagrad by replacing the matrix Addo into the constraint in Eq, (6) Of course, the update procedure Eq. (5) merely a reinterpretation of the original preconditioned update, and thus the employed trust region radii are defined implicitly by the current gradient and stepsize.
Ō Bh- as well for
3.2 DIAGONAL VERSUS FULL PRECONDITIONING
closer look at Figure reveals that the first two problems are perfectly axis-aligned, which makes these objectives particularly attractive for diagonal preconditioning. For comparison, report another quadratic instance, where the Hessian is no longer zero on the off-diagonals (Fig. [ right). As can be seen, this introduces a tilt in the level sets and reduces the superiority of diagonal Adagrad
4

---

Under review as a conference paper at ICLR 2021
over plain GD. However, using the full preconditioner Aada re-establishes the original speed up. Yet, non-diagonal preconditioning comes at the cost of taking the inverse square root of a large matrix, which is why this approach has been relatively unexplored (see Agarwal et al. (2018) for exception). Interestingly, early results by Becker et al. 1988) on the curvature of neural nets report a strong diagonal dominance of the Hessian matrix (wW( However, the reported numbers are only for tiny networks of at most 256 parameters. We here take a first step towards generalizing these findings to modern day networks. Furthermore, we contrast the diagonal dominance of real Hessians the expected behavior of random Wigner matrices | Ordinary Least Squares (OLS) problems with random inputs. For this purpose, let A define the ratio |A.1
For further evidence, we also compare Hessians of
of diagonal to overall mass of a matrix A, i.. ÒA == E.2, JA..) as in (Becker et al. 1988).
Proposition 1 (Diagonal share of Wigner matrix). For random Gaussiar Wigner matrix W (see Eq. (2 the diagonal mass of the expected absolute matrix amounts to: [[[[W]] = I+(--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 (11dd) as the network grows in size. In the following, derive a similar result for the large n limit in the case of OLS Hessians.
Proposition 2 (Diagonal share of OLS Hessian). Let X E R and assume each X.j is generated i.i.d. with zero-mean and finite second moment o² > 0. Then the share of diagonal mass of the v
expected matrix E Hois
amounts to: HF[ "0
(=+(d-1)y
Empirical simulations suggest that this result holds already small n settings (see Figure D.2) and finite n results can be likely derived under assumptions such Gaussian data. As can be seen in Figureßbelove below, even for a practical batch size of n = 32 the diagonal mass ōμ of neural networks stays above both benchmarks for random inputs as well as with real-world data.
40
300
5zl6w
6w/6w
200
20
100
0
Wigner
rand.OLs
rand.NN NN
NN. start
NN during
NN and
Wigner
rand OLS
rand NN
NN start
NN during
NN end
Simple CNN (62k weights)
MLP (41 weights)
Figure 2: Diagonal mass of neural network Hessian 9μ relative to ( and dg H.. of corresponding dimensionality random inputs as well as at random initialization, middle and after reaching 90% training accuracy with RMSProp on CIFAR-10. Mean and 95% confidence interval over 10 independent runs.
These results are in line with Becker et al. (1988) and suggest that full matrix preconditioning might indeed not be worth the additional computational cost. We thus use diagonal preconditioning in all of our experiments in Section 5 but note that further theoretical and empirical claborations of these findings are needed to assess the Hessian structure and hence effectiveness of full-matric pre-conditioning, which is out of the scope of the work at hand.
SECOND-ORDER TRUST REGION METHODS
Cubic regularization (eeterov & Polyak 2006 Cartis et al. 2011) and trust region methods belong to the family of globalized Newton methods. Both frameworks compute parameter updates by
'ff course, Hessians do not have i.i.d. entries but the symmetry of Wigner matrices suggests that this baseline is not completely off.
*The argument naturally extends any distribution with positive expected absolute values.
5

---

Under review as a conference paper at ICLR 2021
optimizing regularized (former) constrained (latter) second-order Taylor models of the objective L around the current iterate W; In particular, in iteration t the update step of the trust region algorithm is computed as
min SER
ms)s) = [(w,) + g + 2 B
B,s s.t. ||||A S...
where A 0 and gi and B, either V((w)) and V ((w, or suitable approximations. The matrix A, induces the shape of the constraint set. So far, the common choice for neural networks A, I, Vi which gives rise spherical trust regions (Xu et al. 2017a Liu et al. 2018). By solving the constrained problem 77. TR methods overcome the problem that pure Newton steps may be ascending, attracted by saddles or not even computable. Please see Appendix for more details.
Why ellipsoids? There are many sources for ill ill-conditioning in neural networks such un-centered and correlated inputs (LeCun et al., 2012), saturated hidden units, and different weight scales in different layers (Van Der Smagt & Hirzinger 1998). While the quadratic term of model 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 Chap. 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 the past and vice versa. Thereby the TR shape is adaptively adjusted to fit the current region of the loss landscape. This not only effective when the iterates are in ill-conditioned neighborhood also helps to escape elongated plateaus (see autoencoder in Sec. Contrary to adaptive first-order methods, the diameter (At) is updated directly depending on whether or not the local Taylor model is an adequate approximation at the current point.
minimizer (Fig. [ but
4.1 CONVERGENCE OF ELLIPSOIDAL. TRUST REGION METHODS
Inspired by the success of adaptive gradient methods, we investigate the use of their preconditioning matrices as norm inducing matrices for second-order TR methods. The crucial condition for con- vergence is that the applied norms 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, := (wT A (wTA,w Aww)// induced by symmetric positive definite matrices A, are called uniformly equivalent, if 3p 2 1 such that Vw E Rd Vt 1,2....
=| S //w/22 S k||w]lA
P
We now establish result which shows that the RMSProp ellipsoid is indeed uniformly equivalent.
Lemma 2 (Uniform equivalence). Suppose lige| 2 < T.Hy for all w, Rdd, 2, Then there always exists e > such that the proposed preconditioning matrices Arms,t (Eq. 3 are uniformly equivalent, i.e. Def. hholds. The same holds for the diagonal variant.
Consequently, the ellipsoids Arms, can directly be applied to any convergent TR framework without losing the guarantee of convergence (Conn et al. (2000). Theorem 6.6.8) In Theorem we extend this result by showing the (to the best of knowledge) first convergence methods. Interestingly, similar results cannot be established for Aada. which reflects the widely known vanishing stepsize problem that arises since squared gradients are continuously added the preconditioning matrix. At least partially, this effect inspired the development of RMSprop (Tieleman Hinton 2012) and Adadelta (Zeiler 2012).
for ellipsoidal TR
'In the following we only TR methods, but we emphasize that the of matrix induced norms can directly he transferred to cubic regularization framework.
'Note that the assumption of bounded batch gradients, i.e. smooth objectives, is common in the analysis of
stochastic algorithms (Allen-Zhu 2017 Defazio al. 2014 Schmidt al. 2017 Duchi al. 201T).

---

Under review as a conference paper at ICLR 2021
4.2 A STOCHASTIC ELLIPSOIDAL 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 a stochastic TR framework in order to circumvent memory issues and reduce the computational complexity. To obtain convergence without computing full derivative information, we first need to assume sufficiently accurate gradient and Hessian estimates.
Assumption (Sufficiently accurate derivatives). The approximations of the gradient and Hessian at step satisfy
ge
VL(ww)ll s &g and |B, - --> бн.
where 0g < (1-n) and 8н I min (1-n)veH 13.fon some 0 < <
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 full 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. 2017; Chen et al., 2018 Blanchet al. 2016) and indeed our experiments in Section 5 use sub-sampled function values due to memory constraints. Secondly, we adapt the framework of Yao et al. (2018); Xu et al. (2077b), which allows for cheap inexact subproblem minimization, the case of iicrationddependent constraint norms (Alg.
Algorithm Stochastic Ellipsoidal Trust Region Method
1: Input: Wy E R y > 1, > 7j > 0, Ao > 0
2: for t- = 0, 1, ... until convergence do
3: Compute approximations g, and B,.
4: If [|ge|] cg. set g: O.
5: Set A; := Arms,t or A, == diag (Arms.t) (see Eq. (3).
6: Obtain s; by solving m, m (5;) approximately.
Compute ratio of function over model decrease: P:. L(w,) L(w, S.) m0(0) -m4
7:
8: Set
S74 11/7
if ps. 2 2
W. + St
if 2 n otherwise
(successful)
A
and We+1
if ps. <
W:
(unsuccessful),
9: end for
Assumption 2(A (Approximate model minimization). Each update step St yields at least as much model decrease the Cauchy- and Eigenpoini simultaneously, (e..,(s)) S mi(s)) and mi ms.))) S my (sf), where Se and s are defined in Eq. (28).
Given that the adaptive norms induced by A Arms, satisfy uniform equivalence shown in Lemma 2 the following Theorem establishes an O (max { 2-=2cm] 2e 3)=3) worst-case iteration complexity
which effectively matches the one of Yao et al. (2018).
Theorem (Convergence rate of Algorithm 1. Assume that L(w) is second-order smooth with Lipschitz constants Lg and LH. Furthermore, let Assumption) [and] hold. Then Algorithum I finds an O(eg, CH) first- and second-ordes stationary point in at most (max {57² 1 . 31) iterations.
The proof of this statement is a straight-forwart forward adaption of the proof for spherical constraints, taking into account that the guaranteed model decrease changes when the computed step s, lies outside the Trust Region. Due to the uniform equivalence established in Lemma the altered diameter of the trust region along that direction and hence the change factor is always strictly positive and finite.
7

---

Under review as a conference paper at ICLR 2021
ResNet18
MLP
Autoencoder
Fashion- Fashion-MMISS MNIST
* >ofootpoppizze
Ta tutire 1a poriii
13 1o0g
CIFAR- 10
Figure 3: Mean and 95% confidence interval of 10 runs. Green dotted line indicates 99% training accuracy.
5 EXPERIMENTS
To validate our claim that ellipsoidal TR methods yield improved performance over spherical ones, we run a set of experiments on two image datasets and three types of network architectures. All methods run on (almost) the same hyperparameters across all experiments (see Table in Appendix B)As depicted in Fig. 3 the ellipsoidal TR methods consistently outperform their spherical counterpart in 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 method, Interestingly, this makes an actual difference in the image reconstruction quality of autoencoders (see Figure 12). where the spherically constrained TR method struggles to escape a saddle. We thus draw the clear conclusion that the ellipsoidal constraints propose are to be preferred over spherical ones when training neural nets with second-order methods. More experimental and architectural details are provided in App. C.
To put the previous results into context, also benchmark several state-of-the -he- gradient methods. For fair comparison, we report results in terms of number of backpropagations, epochs and time. All figures can be found in App. C. Our findings TR method with RMSProp ellipsoids is superior in all metrics, even when benchmarked in terms of time. However, while Fig. 9 indicaaes that ellipsoidal TR methods are slightly superior in terms of backpropagations even for ResNets and Autoencoders, a close look at Fig. [O] revealss that they best manage to keep pace with first-order methods in terms of epochs and are inferior time.
mixed: For small nets such the MLPs the
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 across a large set of experiments. We thus consider the development of further ellipsoids that can potentially adapt even better to the loss landscape such as e.g. (block-) diagonal hessian approximations (e.g. [ekaa et al. (2007)) or approximations of higher order derivatives as an interesting direction of future research.
Interestingly, 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 major obstacle in modern day architectures; 2) The per-iteration time complexity is noticeably lower for first-order methods (Figure ITp. The latter observations suggests that advances in distributed second-orde order algorithms (c.g., Osawa et al.] (2018); Dünner et al. (2018)) constitute a promising direction of research towards the goal of more widespread use of Newton-type methods in deep learning.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang. The case for full-mi full-matrix adaptive regularization. arXiv preprint arXiv: 02958, 2018.
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 Alu,n-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint 1oXIv:2/81..0362,, 2018.
Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):5112776. 1998.
Sue Becker, Yann Le Cun, et al. Improving the convergence of pack-propagttion 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):211--2223 2007.
Jose Blanchet, Coralia Cartis, Matt Menickelly, and Katya Scheinberg. Convergence rate analysis of stochastic trust region method for nonconvex optimization. arXiv preprint 16X1v:1609.0744 2016.
Leon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010 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-311, 2018.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. arXiv preprint arXiv:1702.0796: 2017.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. arXiv preprint
2017.
Coralia Cartis, Nicholas IM Gould, and Philippe L Toint. 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 L. Toint. Complexity bounds for second-order optimality in unconstrained optimization. Journal of Complexity, 28(1):93-100) 2012a.
Coralia Cartis. Nicholas IM Gould, and Philippe L Toint. How Much Patience You Have?: A Worst-case Perspective on 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 2018.
Andrew Conn, Nicholas IM Gould, and Philippe L Toint. Trust region methods. SIAM, 2000.
Frank Curtis and Daniel Robinson. Exploiting negative curvature in deterministic and stochastic optimization. arXiv preprint arXiv:1703.0044 2017.
Frank E Curtis, Daniel P Robinson, and Mohammadreza Samadi. A trust region algorithm with worst-case iteration complexity of (e² for nonconvex optimization. Mathematical Program- ming, 162(1-2):1-32. 2017.

---

Under review as a conference paper at ICLR 2021
Hadi Daneshmand, Jonas Kohler, Aurelien Lucchi, and Thomas Hofmann. Escaping saddles with stochastic gradients. arXiv preprint urXiv:8003: 803.05999, 2018.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem high-dimensional non-convex optimization. In Advances in neural information processing systems, pp. 2933-2944 2014.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in neural information processing systems, pp. 1646-1654, 2014.
Simon S Du and Jason D Lee. On the power of over parametrization in neural networks with quadratic activation. arXiv preprint arXiv: 1803.0/206, 2018.
Simon S Du, Chi Jin, Jason D Lee, Michael I Jordan, Aarti Singh, and Barnabas Poczos. Gradient descent can take exponential time escape saddle points. In 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, 120ml):2121-2159, 2011.
Celestine Dünner, Aurelien Lucchi, Matilde Gargiani, An Bian, Thomas Hofmann, and Martin Jaggi. 2018.
A distributed second-order algorithm you can trust, arXiv preprint
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: httpp://iistill.puu pub/2017 pampl///mmm//mmmmmm/ttttm /ommett
URL
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. International Conference on Machine Learning, pp. 573-582, 2016.
Martin T Hagan and Mohammad B Menhaj. Training feedforward networks with the marquardt algorithm. IEEE transactions on Neural Networks, 5(6)9989-993, 1994.
Geoffrey E Hinton and Ruslan Salakhutdinov. Reducing the dimensionality of data with neural
networks. science, 313(5786):504-577, 2006.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint 17Xiv:1711.04400 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412 2014.
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled cubic regularization for non-convex opti- mization. In International Conference on Machine Learning, 2017.
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 on Learning Theory, pp. 1246-1257, 2016.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. arXiv preprint 1rXiv:1805.08114 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pp. 597-607, 2017.
10

---

Under review as a conference paper at ICLR 2021
Liu Liu, Xuanqing Liu, Cho-Jui Hsieh, and Dacheng Tao. Stochastic recond-orde methods for non-convex optimization with inexact hessian and gradient. arXiv preprint arXiv: 0109.080999.3. 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 1903:v1903.0222 2019.
James Martens. Deep learning via hessian-free optimization. In ICML, volume 27, pp. 735-742, 2010.
James Martens. New insights and perspectives on the natural gradient method. arXiv preprint arXiv:142..1199 2014.
James Martens and Roger Grosse. Optimizing neural networks with kronecker- 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:1804.00 (00.008004..6//2, 2018.
Eiji Mizutani and Stuart Dreyfus. Second-order stagewise backpropagation for messian-matrin analyses and investigation of negative curvature. Neural Networks, 21(2-3):133-233, 2008
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and global performance. Mathematical Programming, 108(1):1772055, 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 181.vv/8/1.12000 2018.
Razvan Pascanu and Yoshua Bengio. Revisiting natural gradient for deep networks. arXiv preprint 1rX15: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):33-112, 2017.
Nicol N Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural computation, 1423):173-17333 2002.
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah. Failures of gradient-based deep learning. 2017.
arXiv preprint
Trond Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20(3):626-637, 1983.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5 6.5-msprop: Divide the gradient by running average its recent magnitude. COURSERA: Neural networks for machine learning. 4(2):26-31, 2012.
11

---

Under review as a conference paper at ICLR 2021
Nilesh Tripuraneni, Mitchell Stern, Chi Jin, Jeffrey Regier, and Michael Jordan. Stochastic cubic regularization for fast nonconvex optimization. arXiv preprint arXiv:1711.02838,, 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.
Rachel Ward, Xiaoxia Wu, and Leon Bottou, Adagrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization. arXiv preprint arXiv:/806.0/8//, 2018.
Eugene P Wigner. Characteristic vectors of bordered matrices with infinite dimensions i. In The Collected Works of Eugene Paul Wigner, pp. 524-540. Springer, 1993.
Peng Xu, Farbod Roosta-Khorasan, and Michael W Mahoney. Second-order optimization for non- convex machine learning: An empirical study. arXiv preprint arXiv: 1708.07877, 2017a.
Peng Xu, Farbod Roosta Khorasani, and Michael W Mahoney. Newton-type methods for non-convex optimization under inxxact hessian information. arXiv preprint 17X0::1708.0711,, 2017b.
Zhewei Yao, Peng Xu, Farbod Koosta-Khorasee and Michael W Mahoney, Inexact non-convex newton-type methods. arXiv preprint arXiv: 180..06900006255 2018.
Matthew D) Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212:5/1 2012.
12


Reviews:
[{"review_id": "jYiVkgDo6L", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "-In section 3.2, the authors use the ratio of the diagonal to the overall mass of a matrix to \"measure\" the quality of diagonal vs full preconditioning. Why this a good measure? motivation and comments about this measure are needed. I think the most important thing to check here is the \"difference\" between A^{-1}g and diag(A)^{-1}g. I think an interesting question that one may investigate here is to link this ratio to the  \"difference\" between A^{-1}g and diag(A)^{-1}g....Or to link this ratio to the complexity...\n\n-In proposition 1, define sigma_1 & 2. I understand that they are defined in the appendix. Just move eq (42) to prop 1. The same about the relation between H & X in proposition 2.\n\n- Rewrite proposition 2, it is a bit misleading, the limit when n goes to infinite should be independent of n ! you may write proportional instead of limit... \n\n-Figure D.2 shows that sqrt(n)/(sqrt(n)+...) decreases to zero with n going to infinite. However, this quantity is non-decreasing as a function of n and it converges to 1 when n diverges!!\n\n-Page 6 after lemma 2, the authors stated that Thm 1 shows the first convergence rate for ellipsoidal TR methods. I disagree about this. The authors may check for instance \nthe work of Conn et al. (this work is cited in the paper) section 6.7  and Bergou et al.: https://link.springer.com/article/10.1007/s10589-017-9929-2  \n\n-  Assumption1: the authors stated that \"For finite-sum objectives such as Eq. (1), the above condition can be met by random sub-sampling due to classical concentration results for sums of random variables\" this is incorrect! take for instance the case where in the finite sum only one term is not zero and all the other are equal to zero. If the non-zero term is not in the sub-sampling for all t the bounds you mentioned may not be satisfied. You can have these bounds but only in a probabilistic manner as in the Blanchet et al. work (this work is cited in the paper)...\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gm5br35wFIU", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes adaptive methods like Adam and AMSProp, and shows that they can be re-interpreted as first order trust region methods with an ellipsoidal trust region (Lemma 1).  The authors then propose a second order trust region method with similar ellipsoidal trust regions induced by the RMSProp matrices (Eq 7). Under some assumptions, they show that this algorithm will converge in a finite number of steps (depending upon the accuracy desired). They also show some experiments to demonstrate their algorithm.\n\nThe approach proposed in the paper is interesting, but the significance of the paper is not clear. The application of ellipsoidal trust region to Newton algorithms can certainly help with the development of new optimizers, but the presented algorithm was not very clear to me: I assume approximate g_t is the minibatch gradient, but how is the approximate B_t computed. How is m_t(s_t) computed approximately? Could you say a little more about Assumptions 1 and 2 - when do they hold? Finally, the experimental results were not very clear - it seems like ellipsoidal TR methods are often outperformed by first order methods. Also no generalization results on test sets were shown.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z7_WLIzVt8N", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes novel stochastic ellipsoidal trust-region methods  inspired by adaptive gradient methods and studies the application of them with adaptive diagonal preconditioners. Theoretical convergence analysis is provided for TR with RMSProp ellipsoid, and numerical results demonstrates the superiority of ellipsoided TR over uniform TR. Interestingly, the paper shows for the first time that, adaptive gradient methods can be view as first-order TR with ellipsoidal constraints. The negative comparative results with state-of-the-art adaptive methods are appreciated, showing that the TR-type methods may not be great choices for deep network training, since the Hessians are often diagonal-dominant in deep-learning practice, and hence the benefit of second-order methods are limited.\n\nAs said, the paper is mostly well-written and present an insightful investigation of stochastic ellipsoidal TR which could be potentially an alternative to state-of-the-art adaptive gradient methods for modern deep network training, and the paper gives a negative answer. On the other hand, the reviewer feels that the potential impact for the deep learning practitioners may be a bit limited and is not very sure about whether the contribution of this work is that significant.\n\nThe experimental details seem unclear. In the experiments, how were the approximate hessian B_t calculated? Are they computed on the same sampled minibatch of gradient or on a new/bigger minibatch? Meanwhile, only training accuracies are reported, which seems inadequate -- should also include the test accuracy plots.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0CkA4tDkUXb", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "Authors propose a new perspective on adaptive gradient methods. Main contribution is a trust region based algorithm they call \"Stochastic Ellipsoidal Trust Region Method\" thats flexible to include both full, and diagonal matrix as the preconditioning matrix.  Authors also mention that the preconditioners are generally diagonally dominant in practice, and may only require diagonal matrix (leaves full matrix for future work).\n\nReason to score:\n\nWeak emperical results, small models, on small datasets without normalizing for batch sizes between experiments.\n\nI have listed my concerns below and hopefully authors can address my concern during the rebuttal period.\n\nI think the authors could substantially improve the emperical results in the paper by including commonly used adaptive methods as baseline (such as Adam), and providing results on stronger baselines, and break down on computational effeciency of the proposed approach in more details.\n\nQuestions/comments:\n\na) There is Appendix C that states that batch size used first order method is 32, vs for this method authors use 128/512 and then compare backprops. This extremely problematic when using # backprop as a way to measure efficiency, as this gives ~4-16x improvement from just larger batch sizes.  I would suggest redoing experiments with exact same batch sizes?\n\nb) Authors indicate using diagonal preconditioner; Could authors consider previous work on kronecker factored preconditioners such as KFAC, or Shampoo that is computationally cheaper in their experiments?\n\nc) Could authors also include walltime comparisons, to split time spent in forward, backward,  hessian-vector product, cg iterations (including details on these as layer sizes increases, for say upto 4k which are common in deep networks trained today?)\n\nd) Could you run a comparison against baselines and settings in: http://www.cs.toronto.edu/~jmartens/docs/Deep_HessianFree.pdf \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers adaptive stochastic optimization methods and shows that they can be re-interpreted as first order trust region methods with an ellipsoidal trust region, they consider a related second order method, and they show convergence properties and empirical results.

The results are of interest, but the significance of some of the results is not clear.  Part of this has to do with substance, and part of this has to do with presentation that can be improved.  Empirical results are weak, including appropriate baselines and details of the empirical results.
Decision: Reject