Title: STOCHASTIC GEODESIC OPTIMIZATION FOR NEURAL NETWORKS

Abstract: We develop a novel and efficient algorithm for optimizing neural networks inspired by a recently proposed geodesic optimization algorithm. Our algorithm, which we call Stochastic Geodesic Optimization (SGeO), utilizes an adaptive coefficient on top of Polyak's Heavy Ball method effectively controlling the amount of weight put on the previous update to the parameters based on the change of direction in the optimization path. Experimental results on strongly convex functions with Lipschitz gradients and deep Autoencoder benchmarks show that SGeO reaches lower errors than established first-order methods and competes well with lower or similar errors to a recent second-order method called K-FAC (Kronecker-Factored Approximate Curvature). We also incorporate Nesterov style lookahead gradient into our algorithm (SGeO-N) and observe notable improvements.

1. INTRODUCTION:

First order methods such as Stochastic Gradient Descent (SGD) with Momentum (Sutskever et al., 2013) and their variants are the methods of choice for optimizing neural networks. While there has been extensive work on developing second-order methods such as Hessian-Free optimization (Martens, 2010) and Natural Gradients (Amari, 1998; Martens & Grosse, 2015) , they have not been successful in replacing them due to their large per-iteration costs, in particular, time and memory. Although Nesterov's accelerated gradient and its modifications have been very effective in deep neural network optimization (Sutskever et al., 2013) , some research have shown that Nesterov's method might perform suboptimal for strongly convex functions (Aujol et al., 2018) without looking at local geometry of the objective function. Further, in order to get the best of both worlds, search for optimization methods which combine the the efficiency of first-order methods and the effectiveness of second-order updates is still underway.

In this work, we introduce an adaptive coefficient for the momentum term in the Heavy Ball method as an effort to combine first-order and second-order methods. We call our algorithm Geodesic Optimization (GeO) and Stochastic Geodesic Optimization (SGeO) (for the stochastic case) since it is inspired by a geodesic optimization algorithm proposed recently (Fok et al., 2017) . The adaptive coefficient effectively weights the momentum term based on the change in direction on the loss surface in the optimization process. The change in direction can contribute as implicit local curvature information without resorting to the expensive second-order information such as the Hessian or the Fisher Information Matrix.

Our experiments show the effectiveness of the adaptive coefficient on both strongly-convex functions with Lipschitz gradients and general non-convex problems, in our case, deep Autoencoders. GeO can speed up the convergence process significantly in convex problems and SGeO can deal with illconditioned curvature such as local minima effectively as shown in our deep autoencoder benchmark experiments. SGeO has similar time-efficiency as first-order methods (e.g. Heavy Ball, Nesterov) while reaching lower reconstruction error. Compared to second-order methods (e.g., K-FAC), SGeO has better or similar reconstruction errors while consuming less memory.

The structure of the paper is as follows: In section 2, we give a brief background on the original geodesic and contour optimization introduced in Fok et al. (2017) , neural network optimization methods and the conjugate gradient method. In section 3, we introduce our adaptive coefficient specifically designed for strongly-convex problems and then modify it for general non-convex cases.

In section 4, we discuss some of the related work in the literature. Section 5 illustrates the algorithm's performance on convex and non-convex benchmarks. More details and insights regarding the algorithm and the experiments can be found in the Appendix.

2. BACKGROUND:



2.1. GEODESIC AND CONTOUR OPTIMIZATION:

The goal is to solve the optimization problem min θ∈R f (θ) where f : R D → R is a differentiable function. Fok et al. (2017) approach the problem by following the geodesics on the loss surface guided by the gradient. In order to solve the geodesic equation iteratively, the authors approximate it using a quadratic. In the neighbourhood of θ t , the solution of the geodesic equation can be approximated as:

θ t+1 = θ t + v t δ t -c t δ 2 t

(1) where θ t is the current point, v t is the unit tangent vector of the geodesic at θ t , δ t is the step size and:

c t = 1 2 ∇f (θ t ) -2(v t • ∇f (θ t ))v t (2)

and θ t+1 is the next point. The tangent vector is estimated by the normalized difference vector between the current point and the previous point v t = θ t -θ t-1 and the first tangent vector is set to the gradient v 1 = ∇f (θ 1 ). For a detailed explanation we refer the reader to Fok et al. (2017) .

2.2. NEURAL NETWORKS:

We consider a neural network with a differentiable loss function f : R D → R with the set of parameters θ. The objective is to minimize the loss function f with a set of iterative updates to the parameters θ. Gradient descent methods propose the following update:

EQUATION

where is the learning rate. However, this update can be very slow and determining the learning rate can be hard. A large learning rate can cause oscillations and overshooting. A small learning rate can slow down the convergence drastically.

Heavy Ball method In order to speed up the convergence of gradient descent, one can add a momentum term (Polyak, 1964) .

d t+1 = µd t -∇f (θ t ); θ t+1 = θ t + d t+1 (4)

where d is the velocity and µ is the momentum parameter.

Nestrov's method Nesterov's accelerated gradient (Nesterov, 1983) according to Sutskever et al.

(2013) can be rewritten as a momentum method:

EQUATION

Nesterov's momentum is different from the heavy ball method only in where we take the gradient.

For the class of convex functions with Lipschitz gradients, Nesterov's momentum is shown to be optimal with a convergence rate of O(1/t 2 ) (Nesterov, 1983) . Note that in both these methods d t is the previous update θ t -θ t-1 .

2.3. CONJUGATE GRADIENTS:

The conjugate gradient algorithm (Hestenes & Stiefel, 1952) attempts to solve the quadratic problem min θ∈R n 1 2 θ T Qθ -b T θ where Q is a n × n positive definite matrix and the update is:

θ t+1 = θ t + t d t ; d t+1 = -g t+1 + γ t d t (6)

where and γ are step sizes and d is the search direction. In the non-quadratic case, min θ∈R n f (θ), the function is locally approximated using a quadratic where g t = ∇f (θ t ) and Q = ∇ 2 f (θ t ) and and γ are:

EQUATION

Clearly, one can see the conjugate gradient method as a momentum method where t is the learning rate and t γ t-1 is the momentum parameter: θ t+1 = θ tt g t + t γ t-1 d t-1 (8) Note that d t = (θ t+1 -θ t )/ t (We added the prime notation to avoid confusion with d t = θ t+1 -θ t throughout the paper). To avoid calculating the Hessian ∇ 2 f which can be very expensive in terms of computation and memory, is usually determined using a line search, i.e. by approximately calculating t = arg min f (θ t + d t ) and several approximations to γ have been proposed. For example, Fletcher & Reeves (1964) have proposed the following:

γ F R t = g t 2 g t-1 2 (9)

Note that γ F R (with an exact line search) is equivalent to the original conjugate gradient algorithm in the quadratic case.

3. STOCHASTIC GEODESIC OPTIMIZATION:

The adaptive coefficient that appears before the unit tangent vector in equation 2 has an intuitive geometric interpretation:

EQUATION

)

where φ t is the angle between the previous update d t = θ t -θ t-1 and the negative of the current gradient -g t . Since 0 ≤ φ ≤ π, thus -1 ≤ cos (π -φ t ) ≤ 1. The adaptive coefficient embeds a notion of direction change on the path of the algorithm which can be interpreted as implicit second-order information. The change in direction at the current point tells us how much the current gradient's direction is different from the previous gradients which is similar to what second-order information (e.g. the Hessian) provide. For more details on the adaptive coefficient we refer the reader to Appendix C.

3.1. STRONGLY CONVEX FUNCTIONS WITH LIPSCHITZ GRADIENTS:

We propose to apply this implicit second-order information to the Heavy Ball method of Polyak (1964) as an adaptive coefficient for the momentum term such that, in strongly-convex functions with Lipschitz gradients, we reinforce the effect of the previous update when the directions align, i.e. in the extreme case: φ = 0 and decrease when they don't, i.e. the other extreme case: φ = π. Thus, we write the coefficient as

γ C t = 1 -ḡt • dt (11) with C indicating "convex". It's obvious that 0 ≤ γ C t ≤ 2.

Note that we will use the bar notation (e.g. d) throughout the paper indicating normalization by magnitude. A μ-strongly convex function f with L-Lipschitz gradients has the following properties:

EQUATION

Applying the proposed coefficient to the Heavy Ball method, we have the following algorithm which we call GeO (Geodesic Optimization):

Algorithm 1: GEO (STRONGLY CONVEX AND LIPSCHITZ) Initialize θ 1 Set d 1 = ∇f (θ 1 ) for t = 1 to T do Calculate the gradient g t = ∇f (θ t ) Calculate adaptive coefficient γ C t = 1 -ḡt • dt Calculate update d t+1 = αγ C t d t -g t Update parameters θ t+1 = θ t + d t+1

where T is total number of iterations and α is a tunable parameter set based on the function being optimized and is the learning rate.

Incorporating Nesterov's momentum We can easily incorporate Nesterov's lookahead gradient into GeO by modifying line 4 to g t = ∇f (θ t + µd t ) which we call GeO-N. In GeO-N the gradient is taken at a further point θ t + µd t where µ is a tunable parameter usually set to a value close to 1.

3.2. NON-CONVEX FUNCTIONS:

However, the algorithm proposed in the previous section would be problematic for non-convex functions such as the loss function when optimizing neural networks. Even if the gradient information was not partial (due to minibatching), the current direction of the gradient cannot be trusted because of non-convexity and poor curvature (such as local minima, saddle points, etc). To overcome this issue, we propose to alter the adaptive coefficient to

γ N C t = 1 + ḡt • dt (13)

with N C indicating "non-convex". By applying this small change we are reinforcing the previous direction when the directions do not agree thus avoiding sudden and unexpected changes of direction (i.e. gradient). In other words, we choose to trust the previous history of the path already taken more, thus acting more conservatively. To increase efficiency, we use minibatches, calling the following algorithm SGeO (Stochastic Geodesic Optimization):

Algorithm 2: SGEO (NON-CONVEX) Initialize θ 1 Set d 1 = ∇f (θ 1 ) for t = 1 to T do Draw minibatch from training set Calculate the gradient g t = ∇f (θ t ) Calculate adaptive coefficient γ N C t = 1 + ḡt • dt Calculate update d t+1 = t γ N C t dt -t ḡt Update parameters θ t+1 = θ t + d t+1

Further we found that using the unit vectors for the gradient ḡ and the previous update d, when calculating the next update in the non-convex case makes the algorithm more stable. In other words, the algorithm behaves more robustly when we ignore the magnitude of the gradient and the momentum term and only pay attention to their directions. Thus, the magnitudes of the updates are solely determined by the corresponding step sizes, which are in our case, the learning rate and the adaptive geodesic coefficient. Same as the strongly convex case, we can integrate Nesterov's lookahead gradient into SGeO by replacing line 5 with g t = ∇f (θ t + µd t ) which we call SGeO-N.

4. RELATED WORK:

There has been extensive work on large-scale optimization techniques for neural networks in recent years. A good overview can be found in Bottou et al. (2018) . Here, we discuss some of the work more related to ours in three parts.

4.1. GRADIENT DESCENT VARIANTS:

Adagrad (Duchi et al., 2011) (Odonoghue & Candes, 2015) proposes to reset the momentum whenever rippling behaviour is observed in accelerated gradient schemes. AggMo (Lucas et al., 2018) keeps several velocity vectors with distinct parameters in order to damp oscillations. AMSGrad (Reddi et al., 2018) on the other hand, keeps a longer memory of the past gradients to overcome the suboptimality of the previous algorithms on simple convex problems. We note that these techniques are orthogonal to our approach and can be adapted to our geodesic update to further improve performance.

4.2. ACCELERATED METHODS:

Several recent works have been focusing on acceleration for gradient descent methods. Meng & Chen (2011) propose an adaptive method to accelerate Nesterov's algorithm in order to close a small gap in its convergence rate for strongly convex functions with Lipschitz gradients adding a possibility of more than one gradient call per iteration. In Su et al. (2014) , the authors propose a differential equation for modeling Nesterov inspired by the continuous version of gradient descent, a.k.a. gradient flow. Wibisono et al. ( 2016) take this further and suggest that all accelerated methods have a continuous time equivalent defined by a Lagrangian functional, which they call the Bregman Lagrangian. They also show that acceleration in continuous time corresponds to traveling on the same curve in spacetime at different speeds. It would be of great interest to study the differential equation of geodesics in the same way. In a recent work, Defazio (2018) proposes a differential geometric interpretation of Nesterov's method for strongly-convex functions with links to continuous time differential equations mentioned earlier and their Euler discretization.

4.3. SECOND-ORDER METHODS:

Second-order methods are desirable because of their fine convergence properties due to dealing with bad-conditioned curvature by using local second-order information. Hessian-Free optimization (Martens, 2010) is based on the truncated-Newton approach where the conjugate gradient algorithm is used to optimize the quadratic approximation of the objective function. The natural gradient method (Amari, 1998) reformulates the gradient descent in the space of the prediction functions instead of the parameters. This space is then studied using concepts in differential geometry. K-FAC (Martens & Grosse, 2015) approximates the Fisher information matrix which is based on the natural gradient method. Our method is different since we are not using explicit second-order information but rather implicitly deriving curvature information using the change in direction.

5. EXPERIMENTS:

We evaluated SGeO on strongly convex functions with Lipschitz gradients and benchmark deep autoencoder problems and compared with the Heavy-Ball and Nesterov's algorithms and K-FAC.

5.1. STRONGLY CONVEX AND LIPSCHITZ FUNCTIONS:

We borrow these three minimization problems from Meng & Chen (2011) where they try to accelerate Nesterov's method by using adaptive step sizes. The problems are Anisotropic Bowl, Ridge Regression and Smooth-BPDN. The learning rate for all methods is set to 1 L except for Nesterov which is set to 4 3L+μ and the momentum parameter µ for Heavy Ball, Nesterov and GeO-N is set to the following:

µ = 1 - √ μ 1 +

√ μ where L is the Lipschitz parameter and μ is the strong-convexity parameter. The adaptive parameter γ t for Fletcher-Reeves is set to γ F R t and for GeO and GeO-N is γ C t = 1 -ḡt • dt . The functionspecific parameter α is set to 1, 0.5 and 0.9 in that order for the following problems. It's important to note that the approximate conjugate gradient method is only exact when an exact line search is used, which is not the case in our experiments with a quadratic function (Ridge Regression).

Anisotropic Bowl:

The Anisotropic Bowl is a bowl-shaped function with a constraint to get Lipschitz continuous gradients:

EQUATION

As in Meng & Chen (2011) , we set n = 500, τ = 4 and θ 0 = τ √ n 1. Thus L = 12nτ 2 + 1 = 96001 and µ = 1. Figure 1 shows the convergence results for our algorithms and the baselines. The algorithms terminate when f (θ) -f * < 10 -12 . GeO-N and GeO take only 82 and 205 iterations to converge, while the closest result is that of Heavy-Ball and Fletcher-Reeves which take approximately 2500 and 3000 iterations respectively.

Ridge Regression:

The Ridge Regression problem is a linear least squares function with Tikhonov regularization:

f (θ) = 1 2 Aθ -b 2 2 + λ 2 θ 2 2 (15)

where A ∈ R m×n is a measurement matrix, b ∈ R m is the response vector and γ > 0 is the ridge parameter. The function f (θ) is a positive definite quadratic function with the unique solution of θ * = (A T A + λI) -1 A T b along with Lipschitz parameter L = A 2 2 + λ and strong convexity parameter μ = λ.

Following Meng & Chen (2011) , m = 1200, n = 2000 and λ = 1. A is generated from U ΣV T where U ∈ R m×m and V ∈ R n×m are random orthonormal matrices and Σ ∈ R m×m is diagonal with entries linearly distanced in [100, 1] while b = randn(m, 1) is drawn (i.i.d) from the standard normal distribution. Thus μ = 1 and L ≈ 1001. Figure 2 shows the results where Fletcher-Reeves, which is a conjugate gradient algorithm, performs better than other methods but we observe similar performances overall except for gradient descent. The tolerance is set to f (θ) -f * < 10 -13 . Smooth-BPDN Smooth-BPDN is a smooth and strongly convex version of the BPDN (basis pursuit denoising) problem: 

EQUATION

√ m • randn(m, 1) is Gaussian noise. Also L = A 2 2 + λ τ + ρ ≈ 502.7.

Since we cannot find the solution analytically, Nesterov's method is used as an approximation to the solution (f * N ) and the tolerance is set to f (θ) -f * N < 10 -12 . Figure 3 shows the results for the algorithms. GeO-N and GeO converge in 308 and 414 iterations respectively, outperforming all other methods. Closest to these two is Fletcher-Reeves with 569 iterations and Nesterov and Heavy Ball converge similarly in 788 iterations.

5.2. DEEP AUTOENCODERS:

To evaluate the performance of SGeO, we apply it to 3 benchmark deep autoencoder problems first introduced in Hinton & Salakhutdinov (2006) which use three datasets, MNIST, FACES and CURVES. Due to the difficulty of training these networks, they have become standard benchmarks for neural network optimization. To be consistent with previous literature (Martens, 2010; Sutskever et al., 2013; Martens & Grosse, 2015) , we use the same network architectures as in Hinton & Salakhutdinov (2006) and also report the reconstruction error instead of the log-likelihood objective. The layer structure for MNIST, FACES and CURVES are [1000 500 250 30 250 500 1000], [2000 1000 500 30 500 1000 2000] and [400 200 100 50 25 6 25 50 100 200 400] respectively. All layers use sigmoid activations except the middle layer for MNIST, the middle and the last layer for FACES and the middle layer for CURVES which use linear activation.

Our baselines are the Heavy Ball algorithm (SGD-HB) (Polyak, 1964) , SGD with Nesterov's Momentum (SGD-N) (Sutskever et al., 2013) and K-FAC (Martens & Grosse, 2015) , a second-order method utilizing natural gradients using an approximation of the Fisher information matrix. Both the baselines and SGeO were implemented using MATLAB on GPU with single precision on a single machine with a 3.6 GHz Intel CPU and an NVIDIA GeForce GTX 1080 Ti GPU with 11 GBs of memory.

The results are shown in Figures 4 to 6. Since we are mainly interested in optimization and not in generalization, we only report the training error, although we have included the test set performances in the Appendix B. We report the reconstruction relative to the computation time to be able to compare with K-FAC, since each iteration of K-FAC takes orders of magnitude longer than SGD and SGeO. The per-iteration graphs can be found in the Appendix A.

All methods use the same parameter initialization scheme known as "sparse initialization" introduced in Martens (2010) . The experiments for the Heavy Ball algorithm and SGD with Nesterov's momentum follow Sutskever et al. ( 2013) which were tuned to maximize performance for these problems. For SGeO, we chose a fixed momentum parameter and used a simple multiplicative schedule for the learning rate:

t = 1 × β t K

where the initial value ( 1 ) was chosen from {0.1,0.15,0.2,0.3,0.4,0.5} and is decayed (K) every 2000 iterations (parameter updates). The decay parameter (β ) was set to 0.95. For the momentum parameter µ, we did a search in {0.999,0.995,0.99}. The minibatch size was set to 500 for all methods except K-FAC which uses an exponentially increasing schedule for the minibatch size. For K-FAC we used the official code provided1 by the authors with default parameters to reproduce the results. The version of K-FAC we ran was the Blk-Tri-Diag approach which achieves the best results in all three cases. To do a fair comparison with other methods, we disabled iterate averaging for K-FAC. It is also worth noting that K-FAC uses a form of momentum (Martens & Grosse, 2015) .

In all three experiments, SGeO-N is able to outperform the baselines (in terms of reconstruction error) and performs similarly as (if not better than) K-FAC. We can see the effect of the adaptive coefficient on the Heavy Ball method, i.e. SGeO, which also outperforms SGD with Nesterov's momentum in two of the experiments, MNIST and FACES, and also outperforms K-FAC in the MNIST experiment. Use of Nesterov style lookahead gradient significantly accelerates training for the MNIST and CURVES dataset, while we see this to a lesser extent in the FACES dataset. This is also the case for the other baselines (Sutskever et al., 2013; Martens & Grosse, 2015) . Further, we notice an interesting phenomena for the MNIST dataset (Figure 4 ). Both SGeO and SGeO-N reach very low error rates, after only 900 seconds of training, SGeO and SGeO-N arrive at an error of 0.004 and 0.0002 respectively.

6. CONCLUSION AND FUTURE WORK:

We proposed a novel and efficient algorithm based on adaptive coefficients for the Heavy Ball method inspired by a geodesic optimization algorithm. We compared SGeO against SGD with Nesterov's Momentum and regular momentum (Heavy Ball) and a recently proposed second-order method, K-FAC, on three deep autoencoder optimization benchmarks and three strongly convex functions with Lipschitz gradients. We saw that SGeO is able to outperform all first-order methods that we compared to, by a notable margin. SGeO is easy to implement and the computational overhead it has over the first-order methods, which is calculating the dot product, is marginal. It can also perform as effectively as or better than second-order methods (here, K-FAC) without the need for expensive higher-order operations in terms of time and memory. We believe that SGeO opens new and promising directions in high dimensional optimization research and in particular, neural network optimization. We are working on applying SGeO to other machine learning paradigms such as CNNs, RNNs and Reinforcement Learning. It remains to analyse the theoretical properties of SGeO such as its convergence rate in convex and non-convex cases which we leave for future work. A AUTOENCODER PER-ITERATION RESULTS

Here we include the per-iteration results for the autoencoder experiments in Figures 7 to 9 . We reported the reconstruction error vs. running time in the main text to make it easier to compare to K-FAC. K-FAC, which is a second-order algorithm, converges in fewer iterations but has a high per-iteration cost. All other methods are first-order and have similar per-iteration costs. 

B GENERALIZATION EXPERIMENTS:

We include generalization experiments on the test set here. However, as mentioned before, our focus is optimization and not generalization, we are aware that the choice of optimizer can have a significant effect on the performance of a trained model in practise. Results are shown in Figures 10 to 12. SGeO-N shows a significant better predictive performance than SGeO on the CURVES data set and both perform similarly on the two other datasets.. Note that the algorithms are tuned for best performance on the training set. Overfitting can be dealt with in various ways such as using appropriate regularization during training and using a small validation set to tune the parameters. Bowl and the Smooth BPDN problem, the values fluctuates between 0 and 2 periodically, with the Smooth-BPDN behaving more sinusoidal and the Anisotropic Bowl more pulse-like. However, for the ridge regression problem, the values gradually increase from 0 in the beginning and stay close to 2 thereafter, indicating φ ≈ 0 (convergence) since γ C = 1 -cos (π -φ) 3 . However, interpreting these values would not be as exact as our convex experiments due to partial gradient information, stochasticity and the non-convex nature of the problems. Further, adding lookahead gradient clearly decreases fluctuations in the adaptive coefficient value, thus a more stable training process. [t] D GLOBAL OPTIMIZATION BENCHMARKS We compared our method (non-stochastic version using γ N C ) with Nesterov's method on global optimization benchmarks with two parameters to facilitate visualization. The results showing the contour plots and the paths taken by the algorithms can be found in Figure 20 .

Levy Function The Levy function (Surjanovic & Bingham; Laguna & Martí, 2005) features a wavy surface in both directions, multiple ravines and local minima. The global minimum is at (0, 0). The function is: f (θ) = sin 2 (πw 1 ) + (w 1 -1) 2 [1 + 10 sin 2 (πw 1 + 1)] + (w 2 -1) 2 [1 + sin 2 (2πw 2 )] (17

)

where w i = 1 + θi-1 4 for i = 1, 2. We initialize all three methods at (9, 10).

Scaled Goldstein-Price Function The scaled Godstein-Price function (Surjanovic & Bingham; Picheny et al., 2013) features several local minima, ravines and plateaus which can be representative

:

http://www.cs.toronto.edu/ jmartens/docs/KFAC3-MATLAB.zip

Figures and Tables:

Figure 1: Anisotropic Bowl

Figure 4: MNIST dataset.

Figure 7: MNIST dataset.

Figure 10: MNIST dataset.

Figure 13 (b) shows the dot product value ḡ • d which is equivalent to cos (π -φ) (where φ is the angle between the previous update and the negative of the current gradient) for different values of φ.Figure 13 (a) shows the adaptive coefficient (γ) behaviour for different values of φ for both convex and non-convex cases. Recall that the adaptive coefficient is used on top the Heavy Ball method. For strongly convex function with Lipschitz gradients we set γ C = 1 -ḡ • d and for non-convex cases γ N C = 1 + ḡ • d.

Figure 13 (b) shows the dot product value ḡ • d which is equivalent to cos (π -φ) (where φ is the angle between the previous update and the negative of the current gradient) for different values of φ.Figure 13 (a) shows the adaptive coefficient (γ) behaviour for different values of φ for both convex and non-convex cases. Recall that the adaptive coefficient is used on top the Heavy Ball method. For strongly convex function with Lipschitz gradients we set γ C = 1 -ḡ • d and for non-convex cases γ N C = 1 + ḡ • d.

Figure 14: Anisotropic Bowl

Figure 17: MNIST dataset.

is an optimization technique that extends gradient descent and adapts the learning rate according to the parameters. Adadelta (Zeiler, 2012) and RMSprop (Tieleman & Hinton, 2012) improve upon Adagrad by reducing its aggressive deduction of the learning rate. Adam (Kingma & Ba, 2014) improves upon the previous methods by keeping an additional average of the past gradients which is similar to what momentum does. Adaptive Restart

Table content: <table/>

S. Surjanovic and D. Bingham. Virtual library of simulation experiments: Test functions and datasets. Retrieved April 14, 2019, from http://www.sfu.ca/ ˜ssurjano. Ilya Sutskever, James Martens, George E Dahl, and Geoffrey E Hinton. On the importance of initialization and momentum in deep learning. ICML (3), 28(1139-1147):5, 2013.

Table content: <table><tr><td>Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by a running</td></tr><tr><td>average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-</td></tr><tr><td>31, 2012.</td></tr><tr><td>Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated</td></tr><tr><td>methods in optimization. proceedings of the National Academy of Sciences, 113(47):E7351-</td></tr><tr><td>E7358, 2016.</td></tr><tr><td>Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv:1212.5701,</td></tr><tr><td>2012.</td></tr></table>

Peer review (iclr2020):
The paper proposes a modification to momentum based optimization algorithms motivated from theory of geodesic optimization algorithms on manifolds. The modification suggested by the paper is to use the normalized inner product between the previous update and the present gradient in the momentum multiplier in standard momentum algorithms like Polyak*s Heavy Ball or Nesterov*s momentum. They propose two DIFFERENT algorithms for strongly convex vs mini-batch non-convex optimization. In essence for STRONGLY CONVEX, the momentum multiplier is INCREASED proportionately when the present negative gradient aligns with the previous update. On the other hand for NON-CONVEX mini batch optimization the update is the exact opposite, the momentum multiplier is INCREASED proportionately when the present negative gradient DOES NOT align with the previous update (essentially treating the newly seen update as an outlier). Experiments are performed with strongly convex objectives and Deep auto encoders. I propose a rating of Weak Reject for the paper. The primary reason for this rating is that while the idea looks interesting and potentially helpful, the treatment of the idea presented in the paper is unfortunately quite PRELIMINARY and leaves much to be desired. The following points detail what I find missing from the paper - 1. More discussion about the intuition wrt Geodesic Optimization - Even though the paper presents itself as a close relative of the Geodesic Optimization, the connection between the presented algorithm and the geodesic optimization seems a little superficial. It would have been great to see a derivation for the algorithm as a special case of the Geodesic optimization on R^d or something to that effect. In absence of such scientific connection - the present motivation seems merely visual. 2. Theoretically grounding at least the convex case - I would have loved to see some analysis of the convex case of the algorithm. Of course one cannot beat the Nesterov acceleration rate in general. In that light, some analysis/discussion as to in which kind of functions one might expect to see a benefit of such a term even on quadratic functions would help to build intuition. At the very least establishing a convergence rate of the same order as Nesterov momentum would be extremely helpful. The purpose of such analysis is no to merely provide a proof but rather to build intuition as well as understand that there are no failure modes for the algorithm. 3. Proposing completely opposite updates for strongly convex and non-convex belie the lack of intuition even more. The authors seem to point to the fact that momentum seems to play different roles for mini batch potentially non-convex optimization and full strongly convex optimization. This is a good understanding to have, one that is still in the process of being better understood in theory. Nevertheless, proposing opposite updates with little discussion seems very preliminary. Maybe a good question to ask here is suppose I wish to do mini-bath convex optimization, which of the two opposite versions would the authors recommend in that scenario? 4. The experiments also are preliminary. They are complete in the full batch strongly convex case, but even in convex cases mini-batch versions seem to be missing and these are important considerations. For non-convex deep learning based experiments - the authors claim that the autoencoders considered in the paper are benchmarks for deep learning optimization but that is unfortunately an outdated viewpoint. While they are definitely the first important cases to verify, to seriously verify the efficacy of the method (especially in the light of no theoretical treatment) it would be good to experiments on larger vision/language models. Overall while I believe that the idea is promising, the treatment of the idea seems preliminary and hence my rating. The authors can certainly improve the paper by adding some analysis/discussion of the algorithm even in simple cases or performing large scale modern experiments to establish practical efficacy. Also I would like to note that the idea of including the inner product of the previous gradient and the present gradient in training dynamics is not completely new even in deep learning. Consider this paper for instance - https://arxiv.org/pdf/1703.04782.pdf- which i think should be cited/compared to.