A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <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> B. High-Order Methods <s> We develop stochastic variants of the wellknown BFGS quasi-Newton optimization method, in both full and memory-limited (LBFGS) forms, for online optimization of convex functions. The resulting algorithm performs comparably to a well-tuned natural gradient descent but is scalable to very high-dimensional problems. On standard benchmarks in natural language processing, it asymptotically outperforms previous stochastic gradient methods for parameter estimation in conditional random fields. We are working on analyzing the convergence of online (L)BFGS, and extending it to nonconvex optimization problems. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <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> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <s> We present a novel per-dimension learning rate method for gradient descent called ADADELTA. The method dynamically adapts over time using only first order information and has minimal computational overhead beyond vanilla stochastic gradient descent. The method requires no manual tuning of a learning rate and appears robust to noisy gradient information, different model architecture choices, various data modalities and selection of hyperparameters. We show promising results compared to other methods on the MNIST digit classification task using a single machine and on a large scale voice dataset in a distributed cluster environment. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <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> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <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> BIB006 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <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> BIB007 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <s> The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at regular intervals, through (sub-sampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise. <s> BIB008 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> B. High-Order Methods <s> We propose a new stochastic L-BFGS algorithm and prove a linear convergence rate for strongly convex and smooth functions. Our algorithm draws heavily from a recent stochastic variant of L-BFGS proposed in Byrd et al. (2014) as well as a recent approach to variance reduction for stochastic gradient descent from Johnson and Zhang (2013). We demonstrate experimentally that our algorithm performs well on large-scale convex and non-convex optimization problems, exhibiting linear convergence and rapidly solving the optimization problems to high levels of precision. Furthermore, we show that our algorithm performs well for a wide-range of step sizes, often differing by several orders of magnitude. <s> BIB009
The second-order method can be used to address the problem where an objective function is highly non-linear and ill-conditioned by introducing curvature information. This section begins with introducing the conjugate gradient method, which is a method that only needs first-order derivative information for well-defined quadratic programming, but overcomes the shortcoming of the steepest descent method, and avoids the disadvantages of Newton's method The solution is global optimal when the objective function is convex. In each parameter update, gradients of total samples need to be calculated, so the calculation cost is high. SGD BIB001 The update parameters are calculated using a randomly sampled minibatch. The method converges at a sublinear rate. The calculation time for each update does not depend on the total number of training samples, and a lot of calculation cost is saved. It is difficult to choose an appropriate learning rate, and using the same learning rate for all parameters is not appropriate. The solution may be trapped at the saddle point in some cases. NAG  Accelerate the current gradient descent by accumulating the previous gradient as momentum and perform the gradient update process with momentum. When the gradient direction changes, the momentum can slow the parameter update speed and reduce the oscillation; when the gradient direction remains, the momentum can accelerate the parameter update. Momentum helps to jump out of locally optimal solution. It is difficult to choose a suitable learning rate. AdaGrad BIB003 The learning rate is adaptively adjusted according to the sum of the squares of all historical gradients. In the early stage of training, the cumulative gradient is smaller, the learning rate is larger, and learning speed is faster. The method is suitable for dealing with sparse gradient problems. The learning rate of each parameter adjusts adaptively. As the training time increases, the accumulated gradient will become larger and larger, making the learning rate tend to zero, resulting in ineffective parameter update. A manual learning rate is still needed. It is not suitable for dealing with non-convex problems. AdaDelta/ RMSProp BIB004 ,  Change the way of total gradient accumulation to exponential moving average. Improve the ineffective learning problem in the late stage of AdaGrad. It is suitable for optimizing non-stationary and non-convex problems. In the late training stage, the update process may be repeated around the local minimum. Adam BIB007 Combining the adaptive methods and the momentum method, the first-order moment estimation and the secondorder moment estimation of the gradient are used to dynamically adjust the learning rate of each parameter, and the bias correction is added. The gradient descent process is relatively stable. It is suitable for most non-convex optimization problems with large data sets and high dimensional space. The method may not converge in some cases. SAG BIB005 The old gradient of each sample and the summation of gradients over all samples are maintained in memory. For each update, one sample is randomly selected each time and the gradient sum is recalculated, and the updated gradient sum is used as the update direction. The method is a linear convergence algorithm, which is much faster than SGD. The method is only applicable to smooth and convex functions and needs to store the gradient of each sample. It is inconvenient to be applied in nonconvex neural networks. SVRG BIB006 Instead of saving the gradient of each sample, the average gradient is saved at regular intervals. and the gradient sum is updated at each iteration by calculating the gradients with respect to the old parameters and the current parameters for the randomly selected samples. It is a linear convergence algorithm. The method does not need to maintain all gradients in memory, which saves memory resources. To apply it to larger/deeper neural nets whose training cost is a critical issue, further investigation is still needed. ADMM  The method solves optimization problems with linear constraints by adding a penalty term to the objective and separating variables into sub-problems which can be solved iteratively. The method uses the separable operators in the convex optimization problem to divide a large problem into multiple small problems that can be solved in a distributed manner. The framework is practical in most large-scale optimization problems. The original residuals and dual residuals are both related to the penalty parameter whose value is difficult to determine. Frank-Wolfe  The method approximates the objective function with a linear function, solves the linear programming to find the feasible descending direction, and makes a one-dimensional search along the direction in the feasible domain. The method can solve optimization problems with linear constraints, whose convergence speed is fast in early iterations. The method converges slowly in later phases. When the iterative point is close to the optimal solution, the search direction and the gradient of the objective function tend to be orthogonal. Such a direction is not the best downward direction. of storing and calculating the inverse Hessian matrix. But note that when applying it to general optimization problems, the second-order gradient is needed to get an approximation to quadratic programming. Then, the classical quasi-Newton method using second-order information is described. Although the convergence of the algorithm can be guaranteed, the computational process is costly and thus rarely used for solving large machine learning problems. In recent years, with the continuous improvement of high-order optimization methods, more and more high-order methods have been proposed to handle large-scale data by using stochastic technique BIB002 , BIB008 , BIB009 . From this perspective, we discuss several highorder methods, including the stochastic quasi-Newton method (integrating the second-order information and the stochastic method) and their variants. These algorithms allow us to use higher-order methods to process large-scale data.