A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Let M(x) denote the expected value at level x of the response to a certain experiment. M(x) is assumed to be a monotone function of x but is unknown to the experimenter, and it is desired to find the solution x = θ of the equation M(x) = α, where a is a given constant. We give a method for making successive experiments at levels x1, x2, ··· in such a way that xn will tend to θ in probability. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Typical methods for gradient descent in neural network learning involve calculation of derivatives based on a detailed knowledge of the network model. This requires extensive, time consuming calculations for each pattern presentation and high precision that makes it difficult to implement in VLSI. We present here a perturbation technique that measures, not calculates, the gradient. Since the technique uses the actual network as a measuring device, errors in modeling neuron activation and synaptic weights do not cause errors in gradient descent. The method is parallel in nature and easy to implement in VLSI. We describe the theory of such an algorithm, an analysis of its domain of applicability, some simulations using it and an outline of a hardware implementation. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> The authors propose a new methodology for creating the first automatically adapting learning rates that achieve the optimal rate of convergence for stochastic gradient descent. Empirical tests agree with theoretical expectations that drift can be used to determine whether the crucial parameter c is large enough. Using this statistic, it will be possible to produce the first adaptive learning rates which converge at optimal speed. > <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> A simple learning rule is derived, the VAPS algorithm, which can be instantiated to generate a wide range of new reinforcement-learning algorithms. These algorithms solve a number of open problems, define several new approaches to reinforcement learning, and unify different approaches to reinforcement learning under a single theory. These algorithms all have guaranteed convergence, and include modifications of several existing algorithms that were known to fail to converge on simple MOPs. These include Q-learning, SARSA, and advantage learning. In addition to these value-based algorithms it also generates pure policy-search reinforcement-learning algorithms, which learn optimal policies without learning a value function. In addition, it allows policy-search and value-based algorithms to be combined, thus unifying two very different approaches to reinforcement learning into a single Value and Policy Search (VAPS) algorithm. And these algorithms converge for POMDPs without requiring a proper belief state. Simulations results are given, and several areas for future research are discussed. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Despite a large literature on upper bounds on complexity of convex optimization, relatively less attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining a understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight minimax complexity estimates for various function classes. We also discuss implications of these results for the understanding the inherent complexity of large-scale learning and estimation problems. <s> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms. <s> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly. <s> BIB008 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Stochastic gradient descent is popular for large scale optimization but has slow convergence asymptotically due to the inherent variance. To remedy this problem, we introduce an explicit variance reduction method for stochastic gradient descent which we call stochastic variance reduced gradient (SVRG). For smooth and strongly convex functions, we prove that this method enjoys the same fast convergence rate as those of stochastic dual coordinate ascent (SDCA) and Stochastic Average Gradient (SAG). However, our analysis is significantly simpler and more intuitive. Moreover, unlike SDCA or SAG, our method does not require the storage of gradients, and thus is more easily applicable to complex problems such as some structured prediction problems and neural network learning. <s> BIB009 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Recurrent Neural Networks (RNNs) are powerful sequence models that were believed to be difficult to train, and as a result they were rarely used in machine learning applications. This thesis presents methods that overcome the difficulty of training RNNs, and applications of RNNs to challenging problems. ::: We first describe a new probabilistic sequence model that combines Restricted Boltzmann Machines and RNNs. The new model is more powerful than similar models while being less difficult to train. ::: Next, we present a new variant of the Hessian-free (HF) optimizer and show that it can train RNNs on tasks that have extreme long-range temporal dependencies, which were previously considered to be impossibly hard. We then apply HF to character-level language modelling and get excellent results. ::: We also apply HF to optimal control and obtain RNN control laws that can successfully operate under conditions of delayed feedback and unknown disturbances. ::: Finally, we describe a random parameter initialization scheme that allows gradient descent with momentum to train RNNs on problems with long-term dependencies. This directly contradicts widespread beliefs about the inability of first-order methods to do so, and suggests that previous attempts at training RNNs failed partly due to flaws in the random initialization. <s> BIB010 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Deep and recurrent neural networks (DNNs and RNNs respectively) are powerful models that were considered to be almost impossible to train using stochastic gradient descent with momentum. In this paper, we show that when stochastic gradient descent with momentum uses a well-designed random initialization and a particular type of slowly increasing schedule for the momentum parameter, it can train both DNNs and RNNs (on datasets with long-term dependencies) to levels of performance that were previously achievable only with Hessian-Free optimization. We find that both the initialization and the momentum are crucial since poorly initialized networks cannot be trained with momentum and well-initialized networks perform markedly worse when the momentum is absent or poorly tuned. ::: ::: Our success training these models suggests that previous attempts to train deep and recurrent neural networks from random initializations have likely failed due to poor initialization schemes. Furthermore, carefully tuned momentum methods suffice for dealing with the curvature issues in deep and recurrent network training objectives without the need for sophisticated second-order methods. <s> BIB011 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> We introduce Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, based on adaptive estimates of lower-order moments. The method is straightforward to implement, is computationally efficient, has little memory requirements, is invariant to diagonal rescaling of the gradients, and is well suited for problems that are large in terms of data and/or parameters. The method is also appropriate for non-stationary objectives and problems with very noisy and/or sparse gradients. The hyper-parameters have intuitive interpretations and typically require little tuning. Some connections to related algorithms, on which Adam was inspired, are discussed. We also analyze the theoretical convergence properties of the algorithm and provide a regret bound on the convergence rate that is comparable to the best known results under the online convex optimization framework. Empirical results demonstrate that Adam works well in practice and compares favorably to other stochastic optimization methods. Finally, we discuss AdaMax, a variant of Adam based on the infinity norm. <s> BIB012 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> We analyze stochastic gradient descent for optimizing non-convex functions. In many cases for non-convex functions the goal is to find a reasonable local minimum, and the main concern is that gradient updates are trapped in saddle points. In this paper we identify strict saddle property for non-convex problem that allows for efficient optimization. Using this property we show that stochastic gradient descent converges to a local minimum in a polynomial number of iterations. To the best of our knowledge this is the first work that gives global convergence guarantees for stochastic gradient descent on non-convex functions with exponentially many local minima and saddle points. Our analysis can be applied to orthogonal tensor decomposition, which is widely used in learning a rich class of latent variable models. We propose a new optimization formulation for the tensor decomposition problem that has strict saddle property. As a result we get the first online algorithm for orthogonal tensor decomposition with global convergence guarantee. <s> BIB013 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> Gradient descent optimization algorithms, while increasingly popular, are often used as black-box optimizers, as practical explanations of their strengths and weaknesses are hard to come by. This article aims to provide the reader with intuitions with regard to the behaviour of different algorithms that will allow her to put them to use. In the course of this overview, we look at different variants of gradient descent, summarize challenges, introduce the most common optimization algorithms, review architectures in a parallel and distributed setting, and investigate additional strategies for optimizing gradient descent. <s> BIB014 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 1) Gradient Descent: <s> We design a stochastic algorithm to train any smooth neural network to $\varepsilon$-approximate local minima, using $O(\varepsilon^{-3.25})$ backpropagations. The best result was essentially $O(\varepsilon^{-4})$ by SGD. ::: More broadly, it finds $\varepsilon$-approximate local minima of any smooth nonconvex function in rate $O(\varepsilon^{-3.25})$, with only oracle access to stochastic gradients. <s> BIB015
The gradient descent method is the earliest and most common optimization method. The idea of the gradient descent method is that variables update iteratively in the opposite direction of the gradients of the objective function. The update is performed to gradually converge to the optimal value of the objective function. The learning rate η determines the step size in each iteration, and thus influences the number of iterations to reach the optimal value BIB014 . Steepest descent algorithm is a widely known algorithm. The idea is to select an appropriate search direction in each iteration so that the value of the objective function minimizes fastest. Gradient descent and steepest descent are not the same, because the direction of the negative gradient does not always descend fastest. Gradient descent is an example of using the Euclidean norm in steepest descent BIB005 . Next, we give the formal expression of gradient descent method. For a linear regression model, we assume that f θ (x) is the function to be learned, J(θ) is the loss function, and θ is the parameter to be optimized iteratively. The goal is to minimize the loss function with where M is the number of training samples, N is the number of input features, x i is an independent variable with x i = (x i 1 , ..., x i N ) for i = 1, ..., M and y i is the target output. The gradient descent alternates the following two steps until it converges: 1) Derive J(θ) for θ j to get the gradient corresponding to each θ j : 2) Update each θ j in the negative gradient direction to minimize the risk function: The gradient descent method is simple to implement. The solution is global optimal when the objective function is convex. It often converges at a slower speed if the variable is closer to the optimal solution, and more iterations need to be performed. Note that all the training data are used in each iteration step, so the gradient descent method is also called the batch gradient descent. If the number of samples is M and the dimension of x is N , the computation complexity for each iteration will be O(M N ). In order to mitigate the cost of computation, some parallelization methods were proposed BIB002 ,  . However, the cost is still hard to accept when dealing with large-scale data. Thus, the stochastic gradient descent method emerges. 2) Stochastic Gradient Descent: Since the batch gradient descent has high computational complexity in each iteration for large-scale data and does not allow online update, stochastic gradient descent (SGD) was proposed BIB001 . The idea of stochastic gradient descent is using one sample randomly to update the gradient per iteration, instead of directly calculating the exact value of the gradient. The stochastic gradient is an unbiased estimate of the real gradient BIB001 . The cost of the stochastic gradient descent algorithm is independent of sample numbers and can achieve sublinear convergence speed BIB009 . SGD reduces the update time for dealing with large numbers of samples and removes a certain amount of computational redundancy, which significantly accelerates the calculation. In the strong convex problem, SGD can achieve the optimal convergence speed  ,  , BIB006 , BIB008 . Meanwhile, it overcomesSince the SGD uses only one sample per iteration, the computation complexity for each iteration is O(N ) where N is the number of features. The update rate for each iteration of SGD is much faster than that of batch gradient descent when the number of samples M is large. SGD increases the overall optimization efficiency at the expense of more iterations, but the increased iteration number is insignificant compared with the high computation complexity caused by large numbers of samples. It is possible to use only thousands of samples overall to get the optimal solution even when the sample size is hundreds of thousands. Therefore, compared with batch methods, SGD can effectively reduce the computational complexity and accelerate convergence. However, one problem in SGD is that the gradient direction oscillates because of additional noise introduced by random selection, and the search process is blind in the solution space. Unlike batch gradient descent which always moves towards the optimal value along the negative direction of the gradient, the variance of gradients in SGD is large and the movement direction in SGD is biased. So, a compromise between the two methods, a mini-batch gradient descent method (MSGD), was proposed BIB001 . The MSGD uses b independent identically distributed samples (b is generally in 50 to 256 BIB014 ) as the sample sets to update the parameters in each iteration. It reduces the variance of the gradients using the mean values of gradients. It makes the convergence more stable, which helps to improve the optimization speed. For brevity, we will call MSGD as SGD in the following sections. As a common feature of stochastic optimization, SGD has a better chance of finding the global optimal solution for complex problems. The deterministic gradient in batch gradient descent may cause the objective function to fall into a local minimum for the multimodal problem. The fluctuation in the SGD helps the objective function jump to another possible minimum. However, the fluctuation in SGD always exists, which slows down the process of converging. There are still many details to be noted about the use of SGD in the concrete optimization process BIB014 , such as the choice of a proper learning rate. A too small learning rate will result in a slower convergence rate, while a too large learning rate will hinder convergence, making loss function fluctuate at the minimum. One way to solve this problem is to set up a predefined list of learning rates or a certain threshold and adjust the learning rate during the learning process BIB001 , BIB003 . However, these lists or thresholds need to be defined in advance according to the characteristics of the dataset. It is also inappropriate to use the same learning rate for all parameters. If data are sparse and features occur at different frequencies, it is not expected to update the corresponding variables with the same learning rate. A higher learning rate is expected for less frequently occurring features BIB007 , BIB012 . Besides the learning rate, how to avoid the objective function being trapped in infinite numbers of the local minimum is a common challenge. Some work has proved that this difficulty does not come from the local minimum values, but comes from the "saddle point" BIB010 . The slope of a saddle point is positive in one direction and negative in another direction, and gradient values in all directions are zero. It is an important problem for SGD to escape from these points. Some research about escaping from saddle points were developed BIB015 , BIB013 . 3) Nesterov Accelerated Gradient Descent: Although SGD is popular and widely used, its learning process is sometimes prolonged. How to adjust the learning rate of the search, how to speed up the convergence, and how to prevent being trapped at a local minimum during the search are worthwhile research directions. Much work is presented to improve the SGD. For example, the momentum idea was proposed to be applied in SGD  . The concept of momentum is derived from the mechanics of physics, which simulates the inertia of objects. The idea of applying momentum in SGD is to preserve the influence of the previous update direction on the next iteration to a certain degree. The momentum method can speed up the convergence when dealing with high curvature, small but consistent gradients, or noisy gradients  . The momentum algorithm introduces the variable v as the speed, which represents the direction and the rate of the parameter's movement in the parameter space. The speed is set as the average exponential decay of the negative gradient. In the gradient descent method, the speed update is v = η · (− ∂J(θ) ∂(θ) ) each time. Using the momentum algorithm, the amount of the update v is not just the amount of gradient descent calculated by η · (− ∂J(θ) ∂(θ) ). It also takes into account the friction factor, which is represented as the previous update amount v old multiplied by a momentum factor ranging between [0, 1]. Generally, the mass of the object is set to 1. The formulation is expressed as where mtm is the momentum factor. If the current gradient is parallel to the previous speed v old , the previous speed can speed up this search. The proper momentum plays a role in accelerating the convergence when the learning rate is small. If the derivative decays to 0, it will continue to update v to reach equilibrium and will be attenuated by friction. It is beneficial for escaping from the local minimum in the training process so that the search process can converge more quickly  , BIB011 . If the current gradient is opposite to the previous update v old , the value v old will have a deceleration effect on this search. The momentum method with a proper momentum factor plays a positive role in reducing the oscillation of convergence when the learning rate is large. How to select the proper size of the momentum factor is also a problem. If the momentum factor is small, it is hard to obtain the effect of improving convergence speed. If the momentum factor is large, the current point may jump out of the optimal value point. Many experiments have empirically verified the most appropriate setting for the momentum factor is 0.9 BIB014 . Nesterov Accelerated Gradient Descent (NAG) makes further improvement over the traditional momentum method BIB011 ,  . In Nesterov momentum, the momentum v old · mtm is added to θ, denoted as θ. The gradient of θ is used in updating. The detailed update formulae for parameters θ are as follows: The improvement of Nesterov momentum over momentum is reflected in updating the gradient of the future position instead of the current position. From the update formula, we can find that Nestorov momentum includes more gradient information compared with the traditional momentum method. Note that Nesterov momentum improves the convergence from O( , when not using stochastic optimization  . Another issue worth considering is how to determine the size of the learning rate. It is more likely to occur the oscillation if the search is closer to the optimal point. Thus, the learning rate should be adjusted. The learning rate decay factor d is commonly used in the SGD's momentum method, which makes the learning rate decrease with the iteration period BIB004 . The formula of the learning rate decay is defined as where η i is the learning rate at the time of the ith iteration, η 0 is the original learning rate, and d is a decimal in [0, 1]. As can be seen from the formula, the smaller the d is, the slower the decay of the learning rate is. The learning rate remains unchanged when d = 0 and the learning rate decays fastest when d = 1.